我正在編寫一個代碼來查找“nx n”矩陣中所有對之間的最短路徑。所以我的代碼似乎正在工作并返回最短路徑。但現在我想記錄頂點之間的路徑，而不僅僅是最短距離。示例 - 城市 1 和 44 之間的最短路徑需要 5 天。現在我想知道它所采用的路徑，在示例中為 1 --> 5 --> 12 --> 44。# The number of verticesnV = len(G)-1print(range(nV))INF = 999# Algorithm implementationdef 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 solutiondef 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)
1 回答
犯罪嫌疑人X
TA貢獻2080條經驗 獲得超4個贊
對Floyd-Warshall算法進行修改：
保留一對(distance, k)，其中k是更新距離值的中間頂點，而不是僅保留距離。k默認值為-1。
if distance[i][j][0] > distance[i][k][0] + distance[k][j][0]:
distance[i][j] = (distance[i][k][0] + distance[k][j][0], k)
您可以通過遞歸重建任何最短路徑。
def get_path(i, j):
if distance[i][j] == +oo: # oo stand for infinite
return [] # None is also an option
k = distance[i][j][1]
if k == -1:
return [i, j]
else:
path = get_path(i, k)
path.pop() # remove k to avoid duplicates
path.extend(get_path(k, j))
return path
運行：O(length of path)
注意：獲得從x到 的最小成本路徑的要求y是從x到的任何路徑之間不存在負成本循環y。
添加回答
舉報
0/150
提交
取消