Python 算法：Floyd-Warshall 全源最短路径算法（Floyd Algorithm）

# /*
# Python 算法：Floyd-Warshall 全源最短路径算法（Floyd Algorithm）
# --------------------------------------------------------
# 原理：
# Floyd 算法用于求解 **任意两点之间** 的最短路径。
# 通过动态规划思想，逐个尝试以每个点作为中转点，
# 若经过该点能使路径更短，则更新距离。
#
# 适用场景：
# - 图中存在正权、负权边（但禁止负环）
# - 需要求所有点对的最短路径
# - 顶点数量较小（一般 V ≤ 400）
#
# 时间复杂度：O(V^3)
# 空间复杂度：O(V^2)
#
# 核心公式：
#     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
#
# dist 初始化方式：
# - 自己到自己为 0
# - 有边的地方填权
# - 无边置为 +∞
# --------------------------------------------------------
# */

import sys

INF = sys.maxsize

# --------------------------------------------------------
# 示例图（邻接矩阵，如果无直连边则设置为 INF）
graph = [
    [0,   3,   INF, 7],
    [8,   0,   2,   INF],
    [5,   INF, 0,   1],
    [2,   INF, INF, 0]
]

# --------------------------------------------------------
def floyd_warshall(graph):
    n = len(graph)
    dist = [row[:] for row in graph]  # 深拷贝矩阵
    next_node = [[None] * n for _ in range(n)]

    # 初始化路径记录表
    for i in range(n):
        for j in range(n):
            if graph[i][j] != INF and i != j:
                next_node[i][j] = j

    # ----------------------------------------------------
    # 三重循环：核心 DP 更新
    for k in range(n):          # 以 k 为中继点
        for i in range(n):      # 起点
            for j in range(n):  # 终点
                if dist[i][k] != INF and dist[k][j] != INF:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        next_node[i][j] = next_node[i][k]

    return dist, next_node

# --------------------------------------------------------
# 路径恢复：从 i 到 j 的实际路径
def get_path(next_node, i, j):
    if next_node[i][j] is None:
        return None
    path = [i]
    while i != j:
        i = next_node[i][j]
        path.append(i)
    return path

# --------------------------------------------------------
# 演示
dist_matrix, next_matrix = floyd_warshall(graph)

print("最短路径矩阵：")
for row in dist_matrix:
    print(row)

print("\n路径示例（0 → 3）：", get_path(next_matrix, 0, 3))
print("最短距离：", dist_matrix[0][3])

# --------------------------------------------------------
# 输出示例：
# 最短路径矩阵：
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]
#
# 路径示例（0 → 3）： [0, 1, 2, 3]
# 最短距离： 6
#
# 要点总结：
# 1) 求所有顶点对的最短路径；
# 2) 可应用于正权、负权图（不能包含负环）；
# 3) 动态规划思想，以第三维 k 控制是否允许使用前 k 个节点作为中转；
# 4) 路径恢复通过 next_node 表完成；
# 5) 对顶点数较多的图性能较差（O(V^3)）。
# */