我正在写一个代码来寻找“nxn”矩阵中所有对之间的最短路径。因此,我的代码似乎正在运行并返回最短路径。但是现在我想记录顶点之间的路径,而不仅仅是最短距离。示例-城市1和44之间的最短路径耗时5天。现在我想知道它所采用的路径,在本例中为1-->;5-->;12-->;44.
# The number of vertices
nV = len(G)-1
print(range(nV))
INF = 999
# Algorithm implementation
def floyd_warshall(G):
distance = list(map(lambda i: list(map(lambda j: j, i)), G))
# Adding vertices individually
for k in range(nV):
for i in range(nV):
for j in range(nV):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
print_solution(distance)
cobalt = list(map(lambda i: list(map(lambda j: j, i)), G))
# Printing the solution
def print_solution(distance):
for i in range(nV):
for j in range(nV):
if(distance[i][j] == INF):
print("INF", end=" ")
else:
print(distance[i][j], end=" ")
cobalt[i][j] = distance[i][j]
print(" ")
abcd = np.asarray(cobalt)
np.savetxt("foo.csv", abcd, delimiter=",")
floyd_warshall(G)
对Floyd Warshall算法进行修改:
保留一对
(distance, k)
,其中k
是更新距离值的中间顶点,而不仅仅是距离。k
的默认值为-1
可以通过递归重构任何最短路径
运行时:
O(length of path)
注意:从
x
到y
的最小成本路径的要求是,从x
到y
的任何路径之间都不存在负成本周期相关问题 更多 >
编程相关推荐