图算法之最短路径Dijkstra算法
一、算法概念
1.作用
只获得了所有节点到初始点的最短路径长度，而非图中各节点之间的最短路径长度
2.限制
Dijkstra算法适用于边权为正的无向和有向图，不适用于有负边权的图！
二、算法思想
节点
- 初始点
- 中继点
- 已求出最短路径的节点
- 未求出最短路径的节点
符号
距离d：
- 若相连，即为边权值
- 若不相连，则设其为无穷大
两个集合S和U：存储最短路径长度
- S：记录已求出最短路径的节点到初始点的最短路径长度
- U：记录未求出最短路径的节点到初始点的最短路径长度
过程
（1）初始化：
- S和U中最短路径长度：直接是初始点到所有节点的距离d
- 初始点在S中，其他点在U中
- 中继点为初始点
（2）移动节点和更新中继点
- 从U集合中选出最短路径长度最小的节点，将其从U集合中移入到S集合中
- 中继点更新为此节点
（3）更新U
- 计算U中的各节点的
路径长度=S中的由初始点到中继点的最短路径长度+初始点到U中各节点的距离d - 比较
路径长度是否小于U中各节点的最短路径长度，若小于，则替换更新。
（4）重复
重复（2）和（3），直到U空，即遍历完所有节点，获得了所有节点到初始点的最短路径长度。