Python - 大規模的Dijkstra算法

Question

我有一個龐大的網絡，大約有400個節點，而我正在嘗試做的是計算您可以在網絡上製作的每條可能路線。這意味着，節點遍歷和從節點1的路徑的總權重到節點2，節點1〜節點3到節點1到節點400

然後，從節點2到節點3，節點2到節點4可達節點2到節點400

（僅供參考，我有蟒蛇的認識非常有限，一天一天，我用HTML/CSS工作）

我一直在使用這個代碼，我發現： http://bytes.com/topic/python/insights/877227-dijkstras-algorithm-finding-shortest-route

但是，由於我的網絡規模龐大，計算從任何節點到任何節點的每種可能方式都需要非常長的時間我。

從我所瞭解的鏈接算法中，它依次從起始節點訪問每個節點，並給它一個值，這是從一開始就到達該節點所需的權重（我想它也會記錄到達每個特定節點所需的路線？）。如果發現到達該節點的路由較短，則會覆蓋之前的節點。一旦到達目的地，它將停止並返回結果。

我想，如果腳本可以稍微編輯一下，是否可以代替在特定目的地停留，只需像往常一樣訪問所有節點，並打印出最短路徑和加權的報告？這樣，算法只需要運行總共400次，每次可能的起始位置一次。

感謝您的任何建議，你可以給我，我希望這是明確的！

Answer 1

您可以使用Python圖表模塊NetworkX，該模塊具有適用於所有配對最短路徑（weighted和unweighted）的方法。而且他們在這種意義上進行了優化，即他們使用最有名的算法來處理這些任務。

Answer 2

你所建議的調整將簡單地改變其排序可能路線的方法，僅此而已。你需要的是通過使用假設來徹底改變遍歷，而且djikstra在大規模實際上並不是那麼高效。