如何使用Floyd-Warshall算法同时获取最短路径及对应最小成本

要在计算全节点对最短路径成本的同时拿到具体路径，只需要在原版算法的基础上，额外维护一个后继节点矩阵即可，具体实现逻辑如下：

1. 矩阵初始化规则 #

你需要同时维护两个二维矩阵：

• 距离矩阵dist：和原版Floyd-Warshall的初始化规则完全一致，dist[i][j]存储节点i到节点j的最短路径成本，初始时dist[i][j]为i到j的直接边权，无边连接时设为无穷大，dist[i][i] = 0
• 后继矩阵next_node：next_node[i][j]存储从节点i出发走最短路径到j时，第一步要跳转的节点。初始时如果i和j有直接边或i==j，next_node[i][j] = j，否则设为-1这类无效值

2. 核心迭代逻辑 #

原版三重循环的松弛逻辑不变，每次用中间节点k尝试优化i到j的路径时，同步更新两个矩阵即可，伪代码如下：

n = 图的总节点数量
INF = 无穷大值
# 初始化矩阵
dist = [[INF] * n for _ in range(n)]
next_node = [[-1] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
    next_node[i][i] = i

# 读入原图的边数据完成初始化
for each edge (u, v, weight):
    dist[u][v] = weight
    next_node[u][v] = v

# Floyd-Warshall主迭代
for k in range(n):
    for i in range(n):
        for j in range(n):
            # 经过k的路径比原路径更短，更新数据
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                next_node[i][j] = next_node[i][k]

3. 最短路径还原方法 #

要获取从起点u到终点v的完整路径，只要沿着next_node矩阵迭代遍历即可：

1. 先判断dist[u][v]是否为无穷大，如果是则说明两点之间没有可达路径
2. 从起点u开始，每次把当前节点加入路径列表，然后跳转到next_node[当前节点][v]，直到当前节点等于v，把v加入列表就得到完整路径

以你举的4到3的路径为例：

• 初始当前节点为4，加入路径，跳转至next_node[4][3] = 2
• 当前节点为2，加入路径，跳转至next_node[2][3] =1
• 当前节点为1，加入路径，跳转至next_node[1][3] =3
• 当前节点为3，加入路径，最终得到路径[4,2,1,3]，和示例完全一致

路径还原的伪代码：

def get_shortest_path(u, v):
    if dist[u][v] == INF:
        return [] # 无可达路径
    path = []
    current = u
    while current != v:
        path.append(current)
        current = next_node[current][v]
    path.append(v)
    return path

注意事项 #

• 该方法和原版Floyd-Warshall一样，不适用存在负权环的图
• 如果节点编号从1开始，只需要调整矩阵下标的初始化范围，逻辑完全不变

内容的提问来源于stack exchange，提问作者Shamim