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 2 + E) .

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

пример

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

темя начальный Step1 V 1 Step2 V 3 Step3 V 2 Step4 V 4 Step5 V 5 Step6 V 7 Step7 V 8 Step8 V 6
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 .

график

На первом этапе все вершины, доступные из источника, обновляются с минимальными затратами. Следовательно, вершины a и h обновляются.

обновленный

На следующем шаге вершины a, b, f и e обновляются.

Следующий путь

Следуя той же логике, на этом шаге вершины b, f, c и g обновляются.

вершины

Здесь вершины c и d обновляются.

Вершины обновлены

Следовательно, минимальное расстояние между вершиной s и вершиной d составляет 20 .

На основании информации предшественника путь s → h → e → g → c → d