Dijkstra算法流程

定义G=(V,E),定义集合S存储已找到最短路径的顶点,集合T存储尚未找到最短路径的顶点,即有t = v-s。

Dijkstra算法描述如下:

(1)假设用加权邻接矩阵边来表示加权有向图,边[i][j]表示弧

(2)选择Vj使得D[j]=Min{D[i]|Vi∈V-S},Vj是从当前找到的Vs开始的最短路径的终点。让S = S ∨{ Vj }

(3)修改从Vs到集合V-S中任意顶点Vk的最短路径长度..如果d[j]+边缘[j] [k]

重复操作(2)(3)***n-1次。由此,获得了从Vs到图上其它顶点的最短路径。