最短路径算法：动态规划与 Dijkstra 算法
Shortest Path Algorithms: Dynamic Programming vs Dijkstra's algorithm
运行 通过动态规划在有向无环图 (DAG) 上使用 memoization 的最短路径算法具有 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 引用的 "arbitrary" 子句。
在你的动态规划中，我认为它不是一个正确的公式，因为它是基于 d(s, u) 已经是 s, u 之间的最短路径这一事实。但你无法证实这一点。确认你应该使用贪心法一步一步得到 "shortest vertices"，这就是 Dijkstra 算法所做的。
而对于动态规划，Floyd–Warshall算法是比较典型的方式，大家可以参考一下http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm。仔细想想！
运行 通过动态规划在有向无环图 (DAG) 上使用 memoization 的最短路径算法具有 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 引用的 "arbitrary" 子句。
在你的动态规划中，我认为它不是一个正确的公式，因为它是基于 d(s, u) 已经是 s, u 之间的最短路径这一事实。但你无法证实这一点。确认你应该使用贪心法一步一步得到 "shortest vertices"，这就是 Dijkstra 算法所做的。
而对于动态规划，Floyd–Warshall算法是比较典型的方式，大家可以参考一下http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm。仔细想想！