Bellman-Ford算法

Question

我知道Bellman-Ford算法最多需要| V | - 如果圖形不包含負重量循環，則重複1次以找到最短路徑。有沒有辦法修改Bellman-Ford算法，以便在1次迭代中找到最短路徑？

Answer 1

不，Bellman-Ford的最壞情況運行時間是O（E * V），這是因爲需要在V-1次上遍歷圖。但是，通過使用基於隊列的貝爾曼變換，我們可以實際上改進Bellman-Ford的運行時間O（E + V）。

這裏是基於隊列的Bellman-Ford實現。從booksite Algorithms, 4th edition, Robert Sedgewick and Kevin Wayne

private void findShortestPath(int src) { 
    queue.add(src); 
    distTo[src] = 0; 
    edgeTo[src] = -1; 
    while (!queue.isEmpty()) { 
     int v = queue.poll(); 
     onQueue[v] = false; 
     for (Edge e : adj(v)){ 
      int w = e.dest; 
      if (distTo[w] > distTo[v] + e.weight) { 
       distTo[w] = distTo[v] + e.weight; 
       edgeTo[w] = v; 
      } 
      if (!onQueue[w]) { 
       onQueue[w] = true; 
       queue.add(w); 
      } 

      //Find if a negative cycle exists after every V passes 
      if (cost++ % V == 0) { 
       if (findNegativeCycle()) 
        return; 
      } 
     } 
    } 
} 

在最壞的情況下運行該算法的時間啓發代碼仍然是O（E * V），但在這種算法通常運行在O（E + V）實際。