--Dijkstra--
流程:
(一) 定义数组: (1)dis(i):表示原点到点i的最短路径
(2)vis(i):标记数组
(3)mp(u,v):邻接表
(二) 使用邻接表mp存图,mp(u,v)=w((u,v,w):u到v的距离为w)
(三) 初始化dis数组(d[s]=0 原点到自己距离为0,d[2~n]其余设为无穷大 1e9)
(四) 遍历(n-1)次 (最后一个点无法更新,确认已经求出最短路径)
(1)遍历dis,求出与原点距离最近的且未被标记的点k
(2)在vis中标记点k
(3)对与点k相连的点v进行松弛操作
(松弛操作:比较 dis(k)+w 与 dis(v),若dis(k)+w<dis(v),将dis(v)更新为dis(k)+w)
(五) 输出dis中每个点与原点的距离
代码示例:
例题:
A569.单源最短路径1
A551.单源最短路径2
A24634.道路削减