算法过程 把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i,j]=d,d表示该路的长度；否则G[i,j]=空值.
定义一个矩阵D用来记录所插入点的信息,D[i,j]表示从Vi到Vj需要经过的点,初始化D[i,j]=j. 把各个顶点插入图中,比较插点后的距离与原来的距离,G[i,j] = min( G[i,j],G[i,k]+G[k,j] ),如果G[i,j]的值变小,则D[i,j]=k.
在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息. 比如,要寻找从V5到V1的路径.
根据D,假如 D(5,1)=3,D(3,1)=2,D(2,1)=1则说明从V5到V1经过V3,从V3到V1经过V2,V2到V1直接相连,路径为 {V5,V3,V2,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连