已经图G的边权矩阵D[1],D[2],D[3]、、、D[n],已经Vi到Vj的最短距离是c,找出Vi到Vj的中间过程.如题.随便写点过程 思路就行.
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/02 00:04:53
![已经图G的边权矩阵D[1],D[2],D[3]、、、D[n],已经Vi到Vj的最短距离是c,找出Vi到Vj的中间过程.如题.随便写点过程 思路就行.](/uploads/image/z/2478831-15-1.jpg?t=%E5%B7%B2%E7%BB%8F%E5%9B%BEG%E7%9A%84%E8%BE%B9%E6%9D%83%E7%9F%A9%E9%98%B5D%5B1%5D%2CD%5B2%5D%2CD%5B3%5D%E3%80%81%E3%80%81%E3%80%81D%5Bn%5D%2C%E5%B7%B2%E7%BB%8FVi%E5%88%B0Vj%E7%9A%84%E6%9C%80%E7%9F%AD%E8%B7%9D%E7%A6%BB%E6%98%AFc%2C%E6%89%BE%E5%87%BAVi%E5%88%B0Vj%E7%9A%84%E4%B8%AD%E9%97%B4%E8%BF%87%E7%A8%8B.%E5%A6%82%E9%A2%98.%E9%9A%8F%E4%BE%BF%E5%86%99%E7%82%B9%E8%BF%87%E7%A8%8B+%E6%80%9D%E8%B7%AF%E5%B0%B1%E8%A1%8C.)
已经图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直接相连