確認爲O Dijkstras算法（V + E）

我正在解決這個問題：確認爲O Dijkstras算法（V + E）

Gaedel教授撰文指出，他聲稱一個程序實現Dijkstra算法。該程序爲V中的每個頂點v生成v.d和v.π。給出一個 O（V + E）時間算法來檢查教授程序的輸出。應該由確定d和π屬性是否匹配某些最短路徑樹的屬性。你可以假定所有的邊權重都是非負的。

VD是從起始節點到v的最短距離 v.π爲v在最短路徑前身從起始節點到v

我的想法是：對於每一個頂點（I），比較用的ID （i.π）.D。如果我的前任有更大的d值，那麼我們不能有最短路徑的樹。

我相信這可以檢查教授的輸出是不是最短路徑樹，但我不認爲它可以確認輸出是最短路徑樹。沒有更多信息，我想不出有辦法做到這一點。

我在正確的軌道上嗎？

來源

2012-11-26 user1754045

在什麼樣的時間你要實現這一點，使用什麼？運行SPA，看看它是不是樹。它是有效的，而且是最有名的。 – ashley

我不確定SPA是什麼。這個問題是從算法第3版的介紹。我想我只需要提供一個通用算法;我不需要指定數據結構。我建議的解決方案在O（E + V）中運行，因爲我訪問過每個頂點和邊，但我不確定它是否正確。 – user1754045

最短路徑算法。 Dijkstra的。最着名的算法之一。 – ashley

我認爲這會工作

做一個DFS，但不是按照常規圖形邊緣，只跟隨每個頂點的π值。你這樣做是爲了產生一個拓撲排序，所以第一個要完成的頂點將是拓撲排序中的第一個頂點。請注意，您生成的地形排序中的第一個頂點將是賦予Gaedel算法的「源」頂點。

現在您已經有了一個topo排序，您可以以最有效的順序放鬆邊界，就像在DAG中執行操作一樣。

for each v in topoSortedVerts 
    if v.d_verify != v.d_Gaedel 
     //fail 

    for each u in v.adjacencies 
     relax(v, u) 

if v.d_verify != v.d_Gaedel 
    //fail

我想你可能還需要確保所有V vert都被考慮，並且源頂點匹配。也許。另外，我猜Gaedel的π值引起的前任子圖可能會被真正擡高，並且會出現各種各樣的瘋狂事情，但我認爲它不會。

它是O(V + E)，因爲外循環運行V次，內循環使用聚合分析運行E次。

來源

2012-11-26 06:06:05 goat

是的，這似乎工作。使用頂級排序查找最短路徑圖與我正在使用的圖相距幾段。這個方法將給出正確的起始頂點，並且應該重新創建由prof創建的最短路徑圖。謝謝您的幫助。 – user1754045

確認爲O Dijkstras算法（V + E）

回答

相關問題