主观题：A dynamic programming perspective on Dijkstra’s Algorithm

Dijkstra’s Algorithm for solving the shortest path problem is generally viewed as a greedy algorithm.

Please try to provide a **dynamic programming** perspective on this algorithm.





答案：每收集一个顶点时，都更新部分顶点的距离最小值，而后一个顶点的更新都是由前一顶点的最优解得来的。
只要记住子问题的最优解，避免重复计算，就是动态规划。
本质上Dijkstra算法可以理解为带权的BFS，只是贪心正好正确，所以得以有效剪枝。