Нахождение минимального пути в нагруженном орграфе

Существует несколько алгоритмов нахождения кратчайшего маршрута в нагруженном графе:

Алгоритм Форда – Беллмана.

Алгоритм Дейкстры.

Пусть Д=(V,X) – нагруженный орграф. V={v₁,…,v_n}.

C(Д)_nxn=[c_ij] – матрица длин дуг нагруженного орграфа.

Величина l_i^(k), где i=1,…,n; k=1,2,… , равна длине минимального пути среди путей из v₁ в v_i, содержащих не более k дуг. Если таких путей нет, то l_i^(k)=¥. l₁⁽⁰⁾ =0, l_i⁽⁰⁾=¥, i=2,…,n.

Утверждение:

При i=2,…,n, k≥0:

При i=1, k≥0:

Число дуг в простой цепи не превосходит n-1. Следовательно,
l_i^(k)= l_i^(n-1) i=2,..,n,k≥n-1.

Если l_i^(n-1)=¥ (i Î {2,..,n}), то v_i не достижима из v₁, а если l_i^(n-1)<¥, то v_i достижима из v₁ и при этом l_i^(n-1) –длина минимального пути из v₁ в v_i.

Таким образом, по l_i^(n-1) можно судить о достижимости вершин v_i (i=2,…,n) из v₁, а также определить длины минимальных путей из v₁ в достижимые вершины.

Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе из v₁ в v_i1 (i1≠1)

Шаг 1: Пусть таблица величин l_i^(k)(i=1,2,…,n;k=0,1,…,n-1) составлена. Если , то вершина не достижима из . В этом случае работа алгоритма заканчивается.

Шаг 2: Пусть . Тогда число выражает длину любого минимального пути из в в нагруженном орграфе Д.

Определим минимальное число k₁≥1, при котором выполняется равенство . По определению чисел l_i^(k) получаем, что k₁ – минимальное число дуг в пути среди всех минимальных путей из в в нагруженном орграфе Д.

Шаг 3: Последовательно определяем номера такие, что:

(*)

Из (*) с учетом того, что ,имеем Þ

(1)

Складывая равенства (*) и учитывая (1) получаем: , т.е. - искомый минимальный путь из в в нагруженном орграфе Д.

В этом пути ровно k₁ дуг. Следовательно, мы определили путь с минимальным числом дуг среди всех минимальных путей из в в нагруженном орграфе Д.