如何记录此关键路径算法中的路径（Python - Floyd Warshall）

Question

我正在编写一个代码来查找“nx n”矩阵中所有对之间的最短路径。所以我的代码似乎正在工作并返回最短路径。但现在我想记录顶点之间的路径，而不仅仅是最短距离。示例 - 城市 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)

Answer 1

对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。