贝尔曼福特和迪杰斯特拉算法区别

贝尔曼福特和迪杰斯特拉算法区别

https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95

贝尔曼福特时间复杂度：O(|V| |E|)

算法伪代码

procedure BellmanFord(list vertices, list edges, vertex source)// 讀入邊和節點的列表並對distance和predecessor寫入最短路徑// 初始化圖 O(|V|)for each vertex v in vertices:if v is source then distance[v] := 0else distance[v] := infinitypredecessor[v] := null// 對每一條邊重複操作 O(|V| |E|)for i from 1 to size(vertices)-1:for each edge (u, v) with weight w in edges:if distance[u] + w < distance[v]:distance[v] := distance[u] + wpredecessor[v] := u// 檢查是否有負權重的回路 O(|E|)for each edge (u, v) with weight w in edges:if distance[u] + w < distance[v]:error "圖包含負權重的回路"

迪杰斯特拉时间复杂度：O(|V|^2) ，dist使用数组实现；O(log|V|(|V|+|E|)) ，dist使用二叉堆实现。使用二叉堆实现时，二叉堆存储的是pair<顶点号, 距离>，表示dist[顶点号]=距离。

伪代码：

 1  function Dijkstra(Graph, source):23      create vertex set Q45      for each vertex v in Graph:            6          dist[v] ← INFINITY                 7          prev[v] ← UNDEFINED                8          add v to Q                     9      dist[source] ← 0                       
10     
11      while Q is not empty:
12          u ← vertex in Q with min dist[u]   
13                                             
14          remove u from Q
15         
16          for each neighbor v of u:           // only v that are still in Q
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:              
19                  dist[v] ← alt
20                  prev[v] ← u
21
22      return dist[], prev[]