通过使用记忆化的动态编程在有向无环图 (DAG) 上运行最短路径算法，其运行时复杂度为 O(V + E)，可以验证使用以下等式:
d(s,v) = min{ d(s,u) + w(u,v) }, over all vertices u->v
现在，Dijkstra 算法还要求图是有向的。使用最小优先级队列，该算法的运行时复杂度为 O(E + V.log(V))，这显然比 DP 的内存版本慢。
根据wiki :
This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.
我在这里遗漏了什么吗？我只是无法消化这里的矛盾..
最佳答案
Dijkstra 算法不限于 DAG；它可以在任何没有负路径权重、循环或其他方式的图上运行。您最有可能提到的拓扑排序不符合您的 Wiki 引用中的“任意”子句。
关于algorithm - 最短路径算法 : Dynamic Programming vs Dijkstra's algorithm，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28145491/