algorithm - Matlab图论渐近复杂度

Question

我最近对图论产生了兴趣，在使用了 MATLAB 的生物信息学工具箱后，我发现 graphshortestpath 函数非常有用。但是，无论我将函数设置为广度优先搜索、Dijkstra 算法还是 Bellman Ford 算法，使用该函数时运行时间总是非常相似。我尝试了从几百到几十万的不同数量的节点，但运行时间仍然几乎相同。

现在，在 MATLAB 网站的 graphshortestpath 页面上，Dijkstra 算法显示的时间复杂度表明它比其他两种算法要快得多。

据我了解，时间复杂度更像是最坏的情况，但我预计运行时间至少会略有不同。

看这里 ( http://www.mathworks.co.uk/help/bioinfo/ref/graphshortestpath.html )

我是不是漏掉了什么？

如有任何帮助，我们将不胜感激。

Answer 1

这里只是一个猜测，但根据您衡量性能的方式，您可能会花费大量时间实际绘制图形路径——这可能比实际搜索花费更多。

尝试在比较之前添加排除绘图过程的计时指标。当然请注意，您的依赖性不仅取决于顶点数，还取决于图中的边数。