Python 算法：Bellman-Ford 最短路径算法（Bellman-Ford Algorithm）

# /*
# Python 算法：Bellman-Ford 最短路径算法（Bellman-Ford Algorithm）
# --------------------------------------------------------
# 原理：
# Bellman-Ford 用于求解含负权边的单源最短路径问题，
# 并且可以检测负权回路（Negative Cycle）。
#
# 基本步骤：
# 1) 将起点距离设为 0，其余设为无穷大；
# 2) 对所有边进行 V-1 次松弛（Relaxation）操作；
# 3) 再执行一次松弛检测是否仍可降低距离：
#       若出现更优解，则存在负权回路。
#
# 特点：
# - 能处理负权边
# - 能检测负权回路
# - 时间复杂度 O(VE)，适合稀疏图
# --------------------------------------------------------
# 图的输入格式：
# edges = [
#     (u, v, w),   # 边：u → v，权重 w
#     ...
# ]
# */

import sys

# --------------------------------------------------------
# 示例图（含负权边，但无负环）
edges = [
    (0, 1, 4),
    (0, 2, 5),
    (1, 2, -3),
    (1, 3, 6),
    (2, 3, 1)
]

num_vertices = 4  # 顶点数量

# --------------------------------------------------------
def bellman_ford(edges, num_vertices, start):
    dist = [sys.maxsize] * num_vertices
    prev = [None] * num_vertices
    dist[start] = 0

    # ------------------------------------------
    # 步骤 1：对所有边进行 V-1 次松弛
    for _ in range(num_vertices - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != sys.maxsize and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                updated = True
        if not updated:
            break  # 若一轮未更新，提前结束

    # ------------------------------------------
    # 步骤 2：检测负权回路
    for u, v, w in edges:
        if dist[u] != sys.maxsize and dist[u] + w < dist[v]:
            print("检测到负权回路！无法求出正确最短路径。")
            return None, None

    return dist, prev

# --------------------------------------------------------
# 工具：恢复路径
def get_path(prev, target):
    if prev[target] is None:
        return [target]
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return list(reversed(path))

# --------------------------------------------------------
# 演示：从 0 号节点出发
distances, predecessors = bellman_ford(edges, num_vertices, 0)

print("最短距离：", distances)
print("前驱数组：", predecessors)
print("\n从 0 到 3 的路径：", get_path(predecessors, 3))

# --------------------------------------------------------
# 输出示例：
# 最短距离： [0, 4, 1, 2]
# 前驱数组： [None, 0, 1, 2]
# 从 0 到 3 的路径： [0, 1, 2, 3]
#
# 要点总结：
# 1) 支持负权边，是 Dijkstra 不能替代的场景；
# 2) 可检测负权回路；
# 3) 复杂度 O(VE)，适合边较少的图；
# 4) 若无负权回路，可以得到精确最短路径；
# 5) 使用前驱数组可重建完整路径。
# */