我实现了从参考书“算法导论”第三版Cormen所找到的Dijkstra算法，用于单源最短路径问题。我的实现是基于Python的，使用链表来表示邻接表中的图。这意味着节点列表是一个链表，每个节点都有一个链接列表来表示每个节点的边缘。此外，我没有实现或使用任何二进制堆或斐波那契堆来作为算法所需的最小优先队列，因此当过程需要提取距离源最近的下一个节点时，我会在节点的链表中搜索每个节点，时间复杂度为O（V）。另一方面，该参考书还提供了一种针对DAG的算法（我已经实现），在应用松弛过程到所有边之前使用拓扑排序。通过所有这些背景，我得到了一个时间复杂度为O（V ^ 2）的Dijkstra算法和一个时间复杂度为O（V + E）的DAG最短路径算法。通过使用timeit.default_timer()函数计算算法的运行时间，我发现当应用于具有正边权重和不同图密度的DAGs时，Dijkstra算法比DAG算法更快，所有这些均适用于100和1000个节点。难道DAG最短路径算法不应该比Dijkstra更快吗？
DAG最短路径与Dijkstra算法的区别
3
- JsMartinez
2
Dijkstra算法对于所有图密度都更快吗？还是只有其中一些？ - NL628
所有的测试用例都跑得更快了。 - JsMartinez
1个回答
2
你对两种算法的运行时间分析是正确的，DAG最短路径算法确实比Dijkstra算法在DAGs上更快。
然而，有三个可能的原因导致你的测试结果：
1. 你用于测试的图非常密集。当图非常密集时，E ≈ V^2，因此两种算法的运行时间接近O(V^2)。 2. 顶点数仍不够大。为了解决这个问题，可以使用更大的图进行进一步测试。 3. DAG的初始化成本很高。
无论如何，理论上DAG最短路径算法应该比Dijkstra算法更快。
然而，有三个可能的原因导致你的测试结果：
1. 你用于测试的图非常密集。当图非常密集时，E ≈ V^2，因此两种算法的运行时间接近O(V^2)。 2. 顶点数仍不够大。为了解决这个问题，可以使用更大的图进行进一步测试。 3. DAG的初始化成本很高。
无论如何，理论上DAG最短路径算法应该比Dijkstra算法更快。
- Hunter Wang
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接