掌握最短路径算法：
Dijkstra, Bellman-Ford 和 Floyd-Warshall

1. 最短路径问题简介

在广阔的计算机科学领域，很少有问题的适用性比“最短路径问题”更普遍。无论是谷歌地图在拥堵的交通中计算最快的回家路线，还是互联网路由器决定如何转发数据包，底层的数学原理都是相同的。

从根本上讲，该问题询问的是：给定一个由节点（位置）和边（连接路径）组成的图，每条边分配有一个“权重”（距离、时间或成本），从起始节点到目标节点使总权重最小的路径是什么？

尽管这个问题听起来很简单，但图的性质（是否为有向图，是否包含负权边，或者是否有环）会彻底改变计算规则，需要采用完全不同的算法方法。在本指南中，我们将解析最短路径算法的三大支柱：Dijkstra、Bellman-Ford 和 Floyd-Warshall。

2. Dijkstra 算法：贪心的工作马

由传奇的荷兰计算机科学家 Edsger W. Dijkstra 在1956年构思，该算法是计算机网络路由和地图导航的无可争议的王者。

策略： Dijkstra 算法使用“贪心”(Greedy) 方法。它总是选择距离源点最近的未访问节点，探索其邻居并更新它们的距离。一旦一个节点被处理，它就被永久地标记为已完成。

工作机制

为了高效地找到当前已知距离最小的节点，Dijkstra 严重依赖 优先队列 (Priority Queue)（通常实现为最小堆 Min-Heap）。

1. 为每个节点分配一个初始距离值：起始节点为 0，所有其他节点为 无穷大。
2. 将起始节点插入优先队列。
3. 当队列不为空时，提取距离最小的节点。
4. 检查此节点的所有未访问邻居。
5. 计算通过当前节点从源点到每个邻居的距离。
6. 如果新计算的距离小于邻居已知的距离，则更新邻居的距离并将其推入优先队列。

Python 实现

import heapq

def dijkstra(graph, start):
    # 将所有距离初始化为无穷大
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    
    # 优先队列存储 (距离, 节点) 元组
    pq = [(0, start)]
    
    while pq:
        # 提取距离最小的节点
        current_distance, current_vertex = heapq.heappop(pq)

        # 如果我们已经找到了更好的路径，则忽略
        if current_distance > distances[current_vertex]:
            continue

        # 检查所有邻居
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # 如果发现更短的路径，则更新
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

致命缺陷：负权边

Dijkstra 的贪心本质使它速度极快 (O((V + E) log V))。然而，这种贪心有一个致命的缺陷：它假设向路径中添加边绝对不会使路径变短。 因此，如果图包含具有 负权 的边，Dijkstra 会惨败，因为一旦一个节点被“完成”，它将永远不会被重新考虑，即使稍后隐藏的负权边可能使到达它的成本更低。

3. Bellman-Ford 算法：处理负权

当你无法保证所有边的权重都是正数时（例如，模拟金融交易，其中某些交易会产生利润而不是成本），Bellman-Ford 就派上用场了。虽然 Dijkstra 是一个贪心算法，但 Bellman-Ford 使用了 动态规划 (Dynamic Programming) 方法。

策略： Bellman-Ford 不是聪明地选择最近的节点，而是采用了一种大锤式的方法：它简单地“松弛”(relax)（更新距离）图中的 每一条边。并且它执行这个过程 V - 1 次。

为什么是 V - 1 次迭代？

一个没有环的图中最长的可能路径最多包含 V - 1 条边（其中 V 是节点的数量）。通过将所有边松弛 V - 1 次，该算法保证距离将稳定在它们的绝对最短值，即使路径必须穿过负权边的迷宫。

负权环检测

Bellman-Ford 最大的超能力是它检测 负权环 的能力。如果在 V - 1 次迭代后，你再松弛一次边，而某个距离 依然 变小，这意味着图具有负权环（一个无限循环，不断降低成本，比如无限的资金套利）。在这种情况下，“最短路径”在数学上是未定义的。

Python 实现

def bellman_ford(graph, V, start):
    # 初始化距离
    distances = {vertex: float('infinity') for vertex in range(V)}
    distances[start] = 0

    # 将所有边松弛 V - 1 次
    for _ in range(V - 1):
        for u, v, w in graph:
            if distances[u] != float('infinity') and distances[u] + w < distances[v]:
                distances[v] = distances[u] + w

    # 运行第 V 次以检查负权环
    for u, v, w in graph:
        if distances[u] != float('infinity') and distances[u] + w < distances[v]:
            print("图包含负权环！")
            return None

    return distances

4. Floyd-Warshall 算法：所有节点对的解决方案

Dijkstra 和 Bellman-Ford 都是 单源 最短路径算法（它们找到从一个起点到所有其他点的路径）。如果你需要同时知道从 每个 节点到 所有其他 节点的最短路径怎么办？

Floyd-Warshall 算法 提供了一个令人难以置信的优雅替代方案。这是另一种动态规划方法，但它在图的整个邻接矩阵上运行。

策略： Floyd-Warshall 系统地检查通过中间节点 k 的路线是否比当前已知的从节点 i 到节点 j 的路线更短。

这个算法的优雅之处在于其三个非常简单的嵌套循环。它非常容易实现，并且对于稠密图非常有用。

Python 实现

def floyd_warshall(graph_matrix, V):
    # 创建图矩阵的副本以存储距离
    dist = [[float('infinity') for _ in range(V)] for _ in range(V)]
    
    # 设置基本情况
    for i in range(V):
        dist[i][i] = 0
    for u in range(V):
        for v in range(V):
            if graph_matrix[u][v] != 0:
                dist[u][v] = graph_matrix[u][v]

    # 核心算法
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # 如果通过 'k' 的路径更短，则更新路径
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                
    return dist

5. 全面比较