找到有向未加權圖中兩個節點之間的所有最短路徑的數量

我需要幫助來找到有向未加權圖中兩個節點之間的所有最短路徑的數量。找到有向未加權圖中兩個節點之間的所有最短路徑的數量

我能夠找到使用BFS算法的最短路徑之一，但我不知道如何找到所有最短路徑。

任何想法的算法/僞代碼，我可以使用？

謝謝！

2016-01-14 Evyatar Elmaliah

您可以通過記住有多少路徑通向每個節點以及發現新節點時總結該數字。

爲簡單起見，我們假設你有定期的BFS算法，每當你使用一個邊緣(u,v)，來電visit(u,v,k)，其中：

u - the source node of the edge 
v - the target node of the edge 
k - the distance from the original source to u

除此之外，假設你有一個映射d:(vertex,distance)->#paths。
這基本上是一個地圖（或2D矩陣），它的關鍵是一對頂點和一個整數 - 距離，它的值是從源到該頂點的最短路徑的數量，距離爲k。

很容易地看到，每個頂點v：

d[v,k] = sum { d[u,k-1] | for all edges (u,v) } 
d[source,0] = 0

而現在，你可以很容易找到的長度k的最短路徑通向每個節點的數量。

優化：

你可以看到「的長度爲k的最短路徑數」是多餘的，你真正需要的k只有一個值的每個頂點。這需要一些記錄，但爲您節省一些空間。

祝你好運！

來源

2016-01-14 19:14:27 amit

我完全失去了這一個。任何人都可以提供僞代碼嗎？ – omerfirmak

修改您的廣度第一次搜索繼續前進，直到它開始找到更長的路徑，而不是停止並返回第一個。

來源

2016-01-14 18:52:09 btilly

你爲什麼認爲它會起作用？可能會有指數數量的最短路徑。 – amit

更明確地說，考慮一個圖：s0-> s1，s0-> s2，s1-> s3，s2-> s3'。這裏有兩條最短的路徑。現在，如果添加's3-> s4，s3-> s5，s4-> s6，s5-> s6'，則有4條最短路徑。再增加一個這樣的部分，將再次加倍最短路徑的數量，等等......等等......如果你只是「繼續直到找到更長的路徑」，BFS將無法找到最短路徑的數量。 – amit

@amit我理解的問題是要真正找到路徑，而不僅僅是數它們。如果有很多路徑，這將是很多工作。 – btilly

浮現在我的腦海裏的第一個想法是下一個：

讓我們命名開始頂點爲s和結束點作爲e。

我們可以存儲兩個數組：D和Q。 D[i]是從s到i和Q[i]的最短路徑的長度，是s和i之間的最短路徑的數量。

我們如何重新計算這些數組？

首先，讓我們設置D[s] = 0和Q[s] = 1。然後我們可以使用衆所周知bfs：

while queue with vertexes is not empty 

    get v from queue 

    set v as visited 

    for all u, there's an edge from v to u 
     if u is not visited yet 
      D[u] = D[v] + 1 
      Q[u] = Q[v] 
      push u into the queue 
     else if D[v] + 1 == D[u] 
      Q[u] += Q[v]

答案是Q[e]。

來源

2016-01-14 19:13:56

找到有向未加權圖中兩個節點之間的所有最短路徑的數量

回答

相關問題