Matlab圖論漸近複雜度

Question

我最近對圖論產生了興趣，並且在用MATLAB生物信息學工具箱進行投資之後，我發現graphshortestpath函數非常有用。但是，使用函數時，運行時間總是非常相似，無論是將函數設置爲廣度優先搜索，Dijkstra算法還是Bellman Ford算法。我嘗試過從幾百到幾十萬不等的節點數量，而且運行時間仍然幾乎相同。

現在在MATLAB網站上的graphshortestpath頁面上，Dijkstra的算法顯示了一個時間複雜度，表明它會比其他兩個算法快得多。

從我所讀的時間複雜度來看，更多的是最糟糕的情況，但我期望在運行時間中看到至少有輕微的差異。

看這裏（http://www.mathworks.co.uk/help/bioinfo/ref/graphshortestpath.html）

我失去了一些東西在這裏？

任何幫助將不勝感激。

Answer 1

這裏只是一個猜測，但取決於您如何衡量性能，您可能會花費大量時間繪製圖表路徑 - 這可能比實際搜索花費更多。

嘗試添加比較前排除繪圖過程的時間度量標準。當然需要注意的是，你的依賴不僅僅取決於頂點的數量，而且取決於你的圖形中邊緣的數量。