4. Dijkstra算法

Dijkstra算法 ： 求图中某一顶点到其余各顶点的最短路径；

算法：

1. 初始化：引入3个辅助数组：dist[ ]，path[ ]，set[ ]，源顶点为v0
   • dist[vi] ：表示当前已找到的源v0到终vi的最短路径长度
     初态：若v0 -> vi上有边(一条边)，则dist[vi]为边上的权值，否则置为∞
   • path[vi] ：表保存从v0到vi最短路径上vi的前一个顶点（也就是中转站）
     初态：若v0 -> vi上有边(一条边直连)，则path[vi] = v0，否则置为path[vi] = -1
   • set[ ] ：为标记数组，set[vi]=0表示vi在T中，即vi没有并入最短路径中；set[vi]=1表示vi在S中，表示已并入最短路径中
     初态：源顶点为1，其余都为0
     [注] S表示已并入最短路径的顶点集合（即set[ ]=1的顶点），T表示未并入最短路径的顶点集（即set[ ]=0的顶点），
2. 执行过程
   (1) 从当前剩余顶点（即set[ ]=0）的顶点的dist[ ]中取最小值，假设为Vu点，将set[Vu]设为1
   (2) 循环扫描图中顶点，对每个顶点做如下检测：设当前扫描的顶点为vj
         §1. 检测vj是否已被并入S，即set[vj]＝1，若是，则跳过它，什么都不做
         §2. 若set[vj] = 0，则比较 dist[vj] 与 dist[Vu]+g[Vu][vj] （g[Vu][vj]表Vu->vj的权值）
             1' 若 dist[vj] <= dist[Vu]+g[Vu][vj]，则什么都不做
             2' 若 dist[vj] > dist[Vu]+g[Vu][vj]，则用右边小的值代替dist[vj]的值，并将path[vj]=Vu
解释：情况2'中dist[Vu]+g[Vu][vj] 小，就是视Vu为中转站，通过中转站Vu使得到vj的距离比它之前的值小，也就是说明了中转站减小了最短路径，并将中转站顶点设为vj的前一个顶点
   (3) 对(1) (2)循环执行n-1次（ｎ为图中顶点的个数），即可得到v0到其余所有顶点的最短路径

[注]

• set[ ]是用来看还有哪些顶点没有加入到最短路径中
• path[ ]是用来看若用来中转站，通过path[ ]可以找到中转这条路径
• dist[ ]是找当前最小的路径长度

---

---

示例：

解析：

推演过程
由上表可知，顶点0到顶点1~6的最短路径长度为 4，5，6，10，9，16
path[] : -1，0，1，0，5，2，4
path[]数组保存的是前驱关系，也就是保存了一棵用双亲存储结构存储的树，通过path[]可打印出从源顶点到任一顶点的最短路径上所经过的所有顶点
借助栈实现逆向输出：

Code

---

---

Dijkstra算法代码实现