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

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

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

В следующем алгоритме мы будем использовать одну функцию 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. Если функция extract min реализована с использованием линейного поиска, сложность этого алгоритма составляетO(V2 + E).

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

пример

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

Вершина Начальная Шаг 1 V 1 Шаг 2 V 3 Шаг 3 V 2 Step4 V 4 Шаг 5 V 5 Шаг 6 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)раз. Следующийfor цикл работает |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