加權圖的BFS算法 - 查找最短距離

我在這個主題上看過不少文章（即post1，post2,post3），但沒有文章提供了一種算法來備份相應的查詢。因此我不確定接受這些帖子的答案。

這裏我介紹一種基於BFS的最短路徑（單源）算法，適用於非負加權圖。任何人都可以幫助我理解爲什麼BFS（根據以下基於BFS的算法）不用於這些問題（涉及加權圖）！加權圖的BFS算法 - 查找最短距離

算法：

SingleSourceShortestPath (G, w, s): 
    //G is graph, w is weight function, s is source vertex 
    //assume each vertex has 'col' (color), 'd' (distance), and 'p' (predecessor) 
     properties 

    Initialize all vertext's color to WHITE, distance to INFINITY (or a large number 
     larger than any edge's weight, and predecessor to NIL 
    Q:= initialize an empty queue 

    s.d=0 
    s.col=GREY  //invariant, only GREY vertex goes inside the Q 
    Q.enqueue(s) //enqueue 's' to Q 

    while Q is not empty 
     u = Q.dequeue() //dequeue in FIFO manner 
     for each vertex v in adj[u] //adj[u] provides adjacency list of u 
      if v is WHITE or GREY  //candidate for distance update 
        if u.d + w(u,v) < v.d  //w(u,v) gives weight of the 
               //edge from u to v 
         v.d=u.d + w(u,v) 
         v.p=u 
         if v is WHITE 
          v.col=GREY //invariant, only GREY in Q 
          Q.enqueue(v) 
         end-if 
        end-if 
       end-if 
     end-for 
     u.col=BLACK //invariant, don't update any field of BLACK vertex. 
         // i.e. 'd' field is sealed 
    end-while

運行：據我看到它是O（| V | + | E |）包括初始化成本

如果這算法類似任何現有的，請讓我知道

來源

2016-07-14 KGhatak

由於僞代碼是Dijksta算法的FIFO隊列，而不是優先級隊列，總是根據距離排序。到目前爲止，每個訪問（黑色）頂點計算出最短距離的關鍵不變量不一定是真實的。這就是爲什麼優先級隊列是（正）加權圖中計算距離的必要條件。

您可以使用算法加權圖表或使其與重量n與1

與反例重量邊連接n-1頂點替換每個邊緣unweighed：

計算的國後第一Q.enqueue(s) ：

一次迭代後計算的狀態：

重要此圖表是一個反是adj[u] = adj[S] = [F, M]和不[M, F]，因此F首先由第二次迭代之後的計算的Q.enqueue(v)

狀態排隊：

由於頂點F首先被出隊u = Q.dequeue()（不同於使用距離優先隊列時），此迭代不會更新任何距離，F將變黑，且不變量將被違反。

國家最後一次迭代後的計算：

來源

2016-07-14 22:02:03

請詳細說明'**這就是爲什麼BFS不用於......'的原因 - 沒有得到你說的原因！ – KGhatak

如果使用隊列而不是優先級隊列，算法會更快並且複雜度更低。但是，對於一些加權圖不會計算最短距離。優先級隊列使Dijkstra算法選擇下一個頂點，以確保爲每個訪問（黑色）頂點計算最短距離。如果使用FIFO隊列，它將無法處理任意的邊權重。你可以在具有圓的小加權圖上找到反例。 –

我已經用循環和自循環進行了測試。我無法理解什麼是「任意」的邊緣權重。你會否提供一個反例！ – KGhatak

它看起來像你實現Dijkstra的經典算法，沒有堆。你正在通過每個邊緣的矩陣，然後看看你是否可以改善距離。

來源

2016-07-14 21:38:17 MathBunny

是的，我的確是放棄了最小堆，發現運行時間比Dijkstra的更好（雖然我獨立做了它，而無需學習的Dijkstra算法中。）。進一步在運行時，Wiki說，用G的鄰接表表示，它是Theta（（| E | + | V |）log | V |），而不是更好的O（| E | + | V |）礦。我也不明白爲什麼BFS算法。對於加權圖幾乎是聞所未聞的。 – KGhatak

加權圖的BFS算法 - 查找最短距離

回答

相關問題