我已经从Cormen的第三版“算法简介”中找到的伪代码实现了Dijkstra算法，用于单源最短路径问题。
我的实现是在python上使用链接列表以邻接列表表示形式表示图的。这意味着节点列表是一个链表，每个节点都有一个链表来表示每个节点的边缘。此外，对于算法所需的最低优先级队列，我没有实现或使用任何二进制堆或斐波那契堆，因此，当过程需要提取时，我会在节点链接列表中的O（V）时间内搜索每个节点。到源的距离最小的下一个节点。
另一方面，参考文献还提供了一种DAG算法（已实现），该算法在将松弛过程应用于所有边缘之前使用拓扑排序。
在所有这些情况下，我有一个Dijkstra算法，其复杂度为
O（V ^ 2）
以及DAG最短路径算法，其复杂度为
O（V + E）
通过使用timeit.default_timer()函数来计算算法的运行时间，我发现Dijkstra算法比应用于具有正边缘权重和不同图形密度的DAG的DAG算法要快，对于100和1000个节点。
对于DAG，DAG最短路径算法是否应该比Dijkstra更快？
您对这两种算法的运行时间分析都是正确的，并且DAG最短路径算法确实比Dijkstra的DAG算法更快。
但是，您的测试结果可能有3个原因：
您用于测试的图形非常密集。当图非常密集时，E≈V ^ 2，因此两种算法的运行时间都接近O（V ^ 2）。
顶点数仍然不够大。为了解决这个问题，您可以使用更大的图形进行进一步测试。
DAG的初始化花费大量的运行时间。
无论如何，理论上DAG最短路径算法应该比Dijkstra的算法更快。