最短路（Shortest Path）

最短路径问题是图论中一个经典问题，目标是找到从一个起点到其他节点的路径，使得路径长度（或权值之和）最小。

---

最短路径的分类

1. 单源最短路径：
   • 给定一个起点 s，求从 s 到图中其他所有节点的最短路径。
   • 算法：Dijkstra、Bellman-Ford。
2. 多源最短路径：
   • 求图中任意两点之间的最短路径。
   • 算法：Floyd-Warshall、Johnson。
3. 单源单终点最短路径：
   • 给定起点 s 和终点 t，求从 s 到 t 的最短路径。
4. 带负权边的最短路径：
   • 图中允许存在负权边。
   • 算法：Bellman-Ford。
5. 单源无权最短路径
   • BFS

---

常用最短路径算法

1. Dijkstra 算法

• 适用范围：单源最短路径，要求所有边的权值非负。
• 基本思想：
  • 使用贪心策略，每次从未处理的节点中选择离起点最近的节点，并更新与其相邻节点的最短距离。
• 算法步骤：
  1. 初始化起点的距离为 0，其他节点的距离为正无穷。
  2. 维护一个优先队列，存储未处理的节点和它们的距离。
  3. 每次选择当前最小距离的节点作为已确定最短路径的节点，更新其邻居节点的距离。
  4. 重复上述过程，直到所有节点的最短距离确定。
• 时间复杂度：
  • 使用邻接矩阵：$O(V^2)$。
  • 使用邻接表 + 优先队列：$O(E\log V)$，适合稀疏图。

Python 示例：

import heapq

def dijkstra(graph, start):
    # graph 是邻接表 {u: [(v, w), ...]}，u 到 v 的权重为 w
    dist = {node: float('inf') for node in graph}  # 初始化所有节点距离为无穷
    dist[start] = 0
    priority_queue = [(0, start)]  # 优先队列存储 (距离, 节点)

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)

        if current_dist > dist[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < dist[neighbor]:
                dist[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return dist

# 示例图
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 6)],
    'C': [('A', 4), ('B', 2), ('D', 3)],
    'D': [('B', 6), ('C', 3)]
}

print(dijkstra(graph, 'A'))  # 输出从 A 到所有节点的最短路径

---

2. Bellman-Ford 算法

• 适用范围：单源最短路径，允许图中有负权边。
• 基本思想：
  • 通过反复“松弛”边的过程更新最短路径。
  • 每次遍历所有边，检查是否可以通过当前边更新某个节点的最短距离。
• 算法步骤：
  1. 初始化起点距离为 0，其他节点距离为正无穷。
  2. 重复 V-1 次（V 是节点数），每次遍历所有边，更新节点的最短距离。
  3. 如果第 V 次遍历时仍然可以更新，说明图中存在负权环。
• 时间复杂度：$O(V\cdot E)$。

Python 示例：

def bellman_ford(graph, start):
    # graph 是边的列表 [(u, v, w)]，u 到 v 的权重为 w
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    for _ in range(len(graph) - 1):
        for u, v, w in graph:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 检测负权环
    for u, v, w in graph:
        if dist[u] + w < dist[v]:
            raise ValueError("图中存在负权环")

    return dist

# 示例图
graph = [
    ('A', 'B', 1),
    ('B', 'C', 2),
    ('A', 'C', 4),
    ('C', 'D', 3),
    ('B', 'D', 6)
]

print(bellman_ford(graph, 'A'))  # 输出从 A 到所有节点的最短路径

---

3. Floyd-Warshall 算法

• 适用范围：多源最短路径。
• 基本思想：
  • 使用动态规划的思想，通过逐步加入节点，更新任意两点之间的最短路径。
  • 每次加入一个中间节点 k，如果路径$i\to k\to j$ 的距离小于 $i\to j$，则更新。
• 算法步骤：
  1. 初始化距离矩阵，直接使用图的权值。
  2. 对每个节点 k，依次更新其他节点 $i,j$ 的距离。
  3. 输出最终的距离矩阵。
• 时间复杂度：$O(V^3)$。

Python 示例：

def floyd_warshall(graph):
    # graph 是邻接矩阵，graph[i][j] 表示 i 到 j 的权重，无连接用 inf 表示
    dist = [[float('inf')] * len(graph) for _ in range(len(graph))]
    
    for i in range(len(graph)):
        for j in range(len(graph)):
            dist[i][j] = graph[i][j]
        dist[i][i] = 0  # 自环距离为 0

    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

# 示例图
graph = [
    [0, 1, 4, float('inf')],
    [1, 0, 2, 6],
    [4, 2, 0, 3],
    [float('inf'), 6, 3, 0]
]

print(floyd_warshall(graph))  # 输出所有节点间的最短路径

---

实际应用

1. 导航与路径规划：
   • Google Maps 等导航软件使用最短路径算法规划路线。
2. 网络路由：
   • 在计算机网络中，路由协议（如 OSPF 和 RIP）使用最短路径算法寻找最优路由。
3. 运输与物流：
   • 寻找最短运输路线，优化物流配送成本。
4. 任务调度与资源分配：
   • 在复杂系统中进行任务调度和资源优化。

---

总结

算法	适用场景	特点	时间复杂度
Dijkstra	单源最短路径，无负权边	贪心算法，高效，适合稀疏图	O(Elog⁡V)O(E \log V)
Bellman-Ford	单源最短路径，允许负权边	动态规划，可检测负权环	O(V⋅E)O(V \cdot E)
Floyd-Warshall	多源最短路径	动态规划，适合稠密图，但时间复杂度较高	O(V3)O(V^3)