[Dijkstra单源最短路径算法]算法思想速成

条件:

1、选定的V0节点

2、邻接矩阵

准备:

1、dist[n]数组:用于记录从V0到Vi的当前最短路径,初始值为邻接矩阵的第0行(也就是V0到各点的直接距离)

2、path[n]数组:用于记录V0到Vi的前一个节点,这样最后可以通过这个得出V0到每个节点的路径,初始值,如果dist[i]!=-1则为0,dist[i]==-1则为-1

算法思想:

1、设定当前定点集只有V0

2、从dist[n]中找到最短的一条路径,指向Vi

3、将Vi归入当前定点集合,并且更新dist[n]和path[n]

  将V0直接到其他节点的长度,和V0通过Vi到其他节点的长度进行比较,如果发现后者更短,则

    更新dist[n]修改为更短的距离

    更新path[n],修改为Vi

大体上就是这样,不断将新的点纳入,不断更新路径,直到把所有点都纳入

最后附上一张图片,但愿看得懂=v=

原文地址:https://www.cnblogs.com/imakoo/p/3498683.html