已经图G的边权矩阵D[1],D[2],D[3]、、、D[n],已经Vi到Vj的最短距离是c,找出Vi到Vj的中间过程.如题.随便写点过程 思路就行.

已经图G的边权矩阵D[1],D[2],D[3]、、、D[n],已经Vi到Vj的最短距离是c,找出Vi到Vj的中间过程.如题.随便写点过程 思路就行.
已经图G的边权矩阵D[1],D[2],D[3]、、、D[n],已经Vi到Vj的最短距离是c,找出Vi到Vj的中间过程.
如题.随便写点过程 思路就行.

已经图G的边权矩阵D[1],D[2],D[3]、、、D[n],已经Vi到Vj的最短距离是c,找出Vi到Vj的中间过程.如题.随便写点过程 思路就行.
算法过程　　把图用邻接矩阵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直接相连