Минимальные маршруты в нагруженных графах

Граф G(V, X) называется нагруженным, если на множестве ребер графа задана функция, называемая весовой, которая ставит в соответствие каждому ребру х Х графа некоторое число l(x). Значение l(x) называется длиной дуги.

Величине l(x) можно придать разный смысл: затраты на транспортировку, время проезда, расстояние между пунктами, расход бензина и т.д.

Сумма длин ребер, входящих в маршрут, называется длиной маршрута.

Заметим, что если для всех х  Х l(x) = 1, то граф можно рассматривать как ненагруженный.

Маршрут в графе G(V, X) из вершины v в вершину w (vw), называется минимальным, если он имеет минимальную длину среди всех маршрутов в графе G(V, X) из вершины v в вершину w.

Ограничимся графами, для которых l(x)>0.

При поиске минимального маршрута в нагруженном графе с l(x)>0

воспользуемся таким же утверждением, что и для ненагруженного графа, а именно:

любой минимальный маршрут является простой цепью.

Рассмотрим теперь задачу поиска минимального маршрута в нагруженном графе.

Пусть граф G(V,X) нагруженный, число вершин n  2, необходимо построить минимальный маршрут из v₁ в v_n.

Приведем алгоритм.

Шаг 1. Каждой вершине присвоить индекс (v_i): (v₁) = 0, (v_i) = , i  1. окрасить вершину v₁ и положить v = v₁.

Шаг 2. Для каждой неокрашенной вершины v_j изменить индекс по правилу:

(v_j) = min {(v_j), (v) + l(v, v_j)}.

Окрасить ту из вершин, для которой (v_j) окажется наименьшим.. окрасить также ребро, ведущее в выбранную на данном шаге вершину v_j . Положить v = v_j.

Шаг 3. Если v = v_j , закончить процедуру, так как кратчайший маршрут из v₁ в v_n . если v  v_n , то перейти к шагу 2.

Замечание. Шаг 2 невозможен, если все (v_j)= . В этом случае вершина v_n недостижима.

Применим изложенный алгоритм к заданному диаграммой графу. Найдем в нем кратчайший маршрут из v₁ в v₆.

Шаг 1. Окрасим вершину v₁ . Присвоим вершинам индексы: (v₁) =0, (v₂) = (v₃)=…= (v_n)=. Полагаем v₁ = v.

Шаг 2.

(v₂) = min {, 0+4} = 4,

(v₃) = min {, 0+7} = 7,

(v₄) = min {, 0+3} = 3,

(v₅) = min {, 0+} = ,

(v₆) = min {, 0+} = .

Окрашиваем вершину v₄ и ребро {v₁, v₄}.

Шаг 3. Так как вершина v₆ не окрашена, выполняем шаг 2, полагая v = v₄.

Шаг 2.

(v₂) = min {4, 3+} = 4,

(v₃) = min {7, 3+} = 7,

(v₅) = min {, 3+3} = 6,

(v₆) = min {, 3+} = .

Окрашиваем вершину v₂ и ребро {v₁, v₂}.

Шаг 3. Так как вершина v₆ не окрашена, выполняем шаг 2, полагая v = v₂.

Шаг 2.

(v₃) = min {7, 4+3} = 7,

(v₅) = min {6, 4+2} = 6,

(v₆) = min {, 4+} = .

Окрашиваем вершину v₅ и ребро {v₄, v₅}.

Шаг 3. Так как вершина v₆ не окрашена, выполняем шаг 2, полагая v = v₅.

Шаг 2.

(v₃) = min {7, 6+} = 7,

(v₆) = min {, 6+2} = 8.

Окрашиваем вершину v₃ и ребро {v₁, v₃}.

Шаг 3. Так как вершина v₆ не окрашена, выполняем шаг 2, полагая v = v₃.

Шаг 2.

(v₆) = min {8, 7+2} = 8.

Окрашиваем вершину v₆ и ребро {v₅, v₆}.

Так как вершина v₆ окрашена, то работу прекращаем. Получили минимальный маршрут v₁ v₄ v₅ v₆ , длина которого равна 8 .

Заметим, что это в данном случае не единственный для вершин v₁ и v₆ минимальный маршрут, т.к. в алгоритме имелась возможность окрасить вместо ребра {v₄, v₅} ребро {v₂, v₅}, тогда бы получили другой маршрут той же длины.