DAA - кратчайшие пути

Алгоритм Дейкстры решает проблему кратчайших путей из одного источника на ориентированном взвешенном графе G = (V, E) , где все ребра неотрицательны (т. Е. W (u, v) ≥ 0 для каждого ребра (u, v). ) Є Д ).

В следующем алгоритме мы будем использовать одну функцию Extract-Min () , которая извлекает узел с наименьшим ключом.

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

Анализ

Сложность этого алгоритма полностью зависит от реализации функции Extract-Min. Если функция извлечения min реализована с использованием линейного поиска, сложность этого алгоритма составляет O (V ² + E) .

В этом алгоритме, если мы используем min-heap, в которой работает функция Extract-Min (), чтобы вернуть узел из Q с наименьшим ключом, сложность этого алгоритма может быть дополнительно уменьшена.

пример

Рассмотрим вершину 1 и 9 как начальную и конечную вершины соответственно. Первоначально все вершины, кроме начальной, отмечены ∞, а начальная вершина — 0 .

темя	начальный	Step1 V ₁	Step2 V ₃	Step3 V ₂	Step4 V ₄	Step5 V ₅	Step6 V ₇	Step7 V ₈	Step8 V ₆
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
3	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

Следовательно, минимальное расстояние вершины 9 от вершины 1 составляет 20 . И путь

1 → 3 → 7 → 8 → 6 → 9

Этот путь определяется на основе информации предшественника.

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

Этот алгоритм решает проблему кратчайшего пути с одним источником для ориентированного графа G = (V, E), в котором веса ребер могут быть отрицательными. Более того, этот алгоритм может быть применен для поиска кратчайшего пути, если не существует отрицательного взвешенного цикла.

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

Анализ

Первый цикл for используется для инициализации, которая выполняется за O (V) раз. Следующий цикл работает | V — 1 | проходит по краям, что занимает O (E) раз.

Следовательно, алгоритм Беллмана-Форда выполняется за время O (V, E) .

пример

В следующем примере показано, как работает алгоритм Беллмана-Форда шаг за шагом. Этот граф имеет отрицательное ребро, но не имеет отрицательного цикла, поэтому проблему можно решить с помощью этой техники.

Во время инициализации все вершины, кроме источника, отмечены ∞, а источник — 0 .