Dijkstra 算法详解

最短路径问题（Shortest Path）是图论研究中经典问题之一，目的是寻找图中两个节点之间最短路径。求解这类问题经典算法有Dijsktra算法、Floyd算法、A*算法等。其中Dijsktra算法最早也最经典。

Dijsktra算法是一种具有贪心思想的动态规划算法。每一步计算都会选择当前最优秀解并更新状态，直到最终状态。Dijsktra算法满足贪心算法基本思想，具有最优子结构性质，因此求出的最短路径序列的子序列也是最短路径，能够保证得到的解是全局最优解。

算法流程

Dijsktra算法可以计算赋权有向无环图中任意节点到其他节点的最短路径。

输入：赋权有向图 G=(V,E,W)，其中V表示图中节点，E表示节点之间的边，W表示权值的集合，即两个节点间距离。起点s 和终点d。

输出：起点s 和终点d的最短路径

算法引入记录中间过程的数组：

• visited 记录已经访问过的节点，避免重复访问
• distance 记录当前所有顶点到s的距离
• parent 记录每个已经求出最短路径的节点的父节点

算法流程如下：

1. 初始化数组，visited记录起点为1,其余节点都为0. distance记录每个节点到s的距离。
2. 在未被访问过的节点中，找到距离s最近的节点u，在visited中标记。
3. 遍历其他节点，如果某节点v到u的距离加上u到s距离之和比distance中记录的距离更小，在distance中更新节点v到s的距离。同时更新parent中v的父节点为u，表示这条路径是s-u-v
4. 重复2,3步骤。直到遍历完所有节点。再查找（s，d）即可得到最短路径和对应距离

Dijsktra算法时间复杂度$O(n^2)$