尋找最短路徑數的算法

給定一個無向（無長度）圖G =（V，E），其中| V | = n和| E | = m，並且兩個頂點v，w找到算法輸出在G.運行時間最短的VW-路徑的數量應該是O（M + N）尋找最短路徑數的算法

我已被這個問題工作，但有困難讓運行時間爲O（M + N）

既然這個圖是無向和不加權的，我已經試過這種方式。使用BFS來確定最短v-w路徑的長度。然後使用DFS查找v-w最短路徑的數量，以便連接兩個節點，路徑長度等於BFS的輸出。但是這個計劃的運行時間是O（m + n）+ O（m + n）。

另外我試過修改Dijkstra算法。存儲添加到訪問節點集合的節點時，存儲最短路徑的長度和最短路徑的編號。而且我堅持計算運行時間。

來源

2014-09-12 Bowen Sun

你已經試過了什麼？ – thb 2014-09-12 21:55:35

當你發佈信息時，請告訴你已經嘗試了什麼，所以它看起來並不像你剛纔詢問你的行爲的答案，甚至沒有在第一時間找到它，我肯定不是這樣的;） – Mitvailer 2014-09-12 22:33:46

我假設邊緣未加權？ – templatetypedef 2014-09-12 22:45:44

此問題可能正在尋找修改Dijsktra's algorithm。使用Dijkstra的算法，您可以爲每個節點維護到該節點的最短路徑的長度，並且您可以根據到相鄰節點的最短路徑以及從該相鄰節點到節點的簡單鏈路的長度有問題。

在每個節點上，您可以保留最短路徑的長度以及最短路徑的長度，可以在其最短路徑上的節點表以及該節點的最短路徑數量應該是這些鄰居的最短路徑數量的總和。當找到到節點的新的最短路徑時，要麼刪除所有這些信息（如果新的最短路徑比以前更短），要麼更新路徑中倒數第二個節點的表中的條目，如果新路徑是與先前到該節點的最短路徑的長度相同。

來源

2014-09-13 04:41:44 mcdowella

非常感謝。這非常有幫助。您能否給我一些關於運行時間的更多信息？我不擅長確定給定算法的運行時間，我非常想知道如何去做。你能幫我嗎？ – 2014-09-13 23:55:07

查看維基百科中的複雜信息，可以看到您只需訪問一次頂點，而對於大型圖形，您大部分時間都需要運行優先級隊列計算來計算首先訪問哪個頂點。當你訪問一個頂點時，你需要添加或修改一個表項並增加一些路徑或者清除一個表項。清算表格可能意味着要刪除許多條目，但如果您在創建每個條目時考慮了此成本，則這只是每條條目的少量成本。所以我懷疑這些額外的工作是否會影響O（n）的成本。 – mcdowella 2014-09-14 05:07:28

您可以在O（N）中找到使用修改的BFS的不同路徑的數量。這裏是solution。

來源

2014-09-14 15:54:42 Zoli

尋找最短路徑數的算法

回答

相關問題