更新时间:2022-12-17 11:01:48
您必须在if语句中添加一个新的矩阵来存储路径重建数据(数组 p
是前一个矩阵):
You have to add to your if statement a new matrix to store path reconstruction data (array p
which is predecessor matrix):
if graph[i,j] > graph[i,k] + graph[k,j]:
graph[i,j] = graph[i,k] + graph[k,j]
p[i,j] = p[k,j]
在开始时,矩阵 p
必须填写为:
At the beginning the matrix p
have to be filled as:
for i in range(0,v):
for j in range(0,v):
p[i,j] = i
if (i != j and graph[i,j] == 0):
p[i,j] = -30000 # any big negative number to show no arc (F-W does not work with negative weights)
要重建 i
和 j
节点之间的路径,您必须调用:
To reconstruct the path between i
and j
nodes you have to call:
def ConstructPath(p, i, j):
i,j = int(i), int(j)
if(i==j):
print (i,)
elif(p[i,j] == -30000):
print (i,'-',j)
else:
ConstructPath(p, i, p[i,j]);
print(j,)
以及具有以上功能的测试:
And the test with above function:
import numpy as np
graph = np.array([[0,10,20,30,0,0],[0,0,0,0,0,7],[0,0,0,0,0,5],[0,0,0,0,10,0],[2,0,0,0,0,4],[0,5,7,0,6,0]])
v = len(graph)
# path reconstruction matrix
p = np.zeros(graph.shape)
for i in range(0,v):
for j in range(0,v):
p[i,j] = i
if (i != j and graph[i,j] == 0):
p[i,j] = -30000
graph[i,j] = 30000 # set zeros to any large number which is bigger then the longest way
for k in range(0,v):
for i in range(0,v):
for j in range(0,v):
if graph[i,j] > graph[i,k] + graph[k,j]:
graph[i,j] = graph[i,k] + graph[k,j]
p[i,j] = p[k,j]
# show p matrix
print(p)
# reconstruct the path from 0 to 4
ConstructPath(p,0,4)
输出:
p:
[[ 0. 0. 0. 0. 5. 1.]
[ 4. 1. 5. 0. 5. 1.]
[ 4. 5. 2. 0. 5. 2.]
[ 4. 5. 5. 3. 3. 4.]
[ 4. 5. 5. 0. 4. 4.]
[ 4. 5. 5. 0. 5. 5.]]
路径0-4:
0
1
5
4