编辑“︁最短路径问题”︁（章节）

= 最短路径问题 =

最短路径问题是'''图论算法'''中的经典问题，旨在寻找图中两个节点之间的最短路径（即路径上所有边的权重之和最小）。它在现实生活中有着广泛的应用，例如导航系统、网络路由、物流配送等。

== 基本概念 ==

在图论中，最短路径问题通常分为以下几种类型：
* '''单源最短路径'''（Single-Source Shortest Path, SSSP）：从一个固定起点到图中所有其他节点的最短路径。
* '''多源最短路径'''（All-Pairs Shortest Path, APSP）：计算图中任意两个节点之间的最短路径。
* '''单目标最短路径'''（Single-Destination Shortest Path）：从所有节点到一个固定终点的最短路径（可通过反向图转换为SSSP）。

=== 图的表示 ===
图可以用'''邻接矩阵'''或'''邻接表'''表示：
* '''邻接矩阵'''：适合稠密图（边数接近节点数的平方），空间复杂度为<math>O(V^2)</math>。
* '''邻接表'''：适合稀疏图（边数远小于节点数的平方），空间复杂度为<math>O(V + E)</math>。

以下是一个简单的无向图示例：
<mermaid>
graph LR
    A -- 5 --> B
    A -- 1 --> C
    B -- 2 --> C
    B -- 3 --> D
    C -- 4 --> D
</mermaid>

== 常见算法 ==

=== 1. Dijkstra算法 ===
'''Dijkstra算法'''适用于'''非负权重'''的图，采用贪心策略逐步扩展最短路径树。

==== 算法步骤 ====
1. 初始化：起点距离为0，其他节点距离为无穷大（∞）。
2. 选择当前距离最小的未访问节点。
3. 更新其邻居节点的距离。
4. 重复步骤2-3，直到所有节点被访问。

==== 代码示例 ====
<syntaxhighlight lang="python">
import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# 示例图（邻接表表示）
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 3},
    'C': {'A': 1, 'B': 2, 'D': 4},
    'D': {'B': 3, 'C': 4}
}

print(dijkstra(graph, 'A'))
</syntaxhighlight>

==== 输出 ====
<pre>
{'A': 0, 'B': 3, 'C': 1, 'D': 5}
</pre>

=== 2. Bellman-Ford算法 ===
'''Bellman-Ford算法'''可以处理负权重边，并能检测负权环。

==== 算法步骤 ====
1. 初始化所有节点距离为∞，起点距离为0。
2. 对每条边进行松弛操作（即尝试缩短路径）。
3. 重复步骤2共<math>V-1</math>次。
4. 检查是否存在负权环。

==== 代码示例 ====
<syntaxhighlight lang="python">
def bellman_ford(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight
    
    # 检查负权环
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                raise ValueError("图中存在负权环")
    
    return distances

# 示例图（含负权重）
graph = {
    'A': {'B': -1, 'C': 4},
    'B': {'C': 3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}

print(bellman_ford(graph, 'A'))
</syntaxhighlight>

==== 输出 ====
<pre>
{'A': 0, 'B': -1, 'C': 2, 'D': -2, 'E': 1}
</pre>

=== 3. Floyd-Warshall算法 ===
'''Floyd-Warshall算法'''用于多源最短路径，支持负权重边（但不能有负权环）。

==== 算法步骤 ====
1. 初始化距离矩阵。
2. 通过中间节点更新所有节点对的距离。
3. 重复步骤2共<math>V</math>次。

==== 代码示例 ====
<syntaxhighlight lang="python">
def floyd_warshall(graph):
    nodes = list(graph.keys())
    n = len(nodes)
    dist = [[float('infinity')] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
        for neighbor, weight in graph[nodes[i]].items():
            j = nodes.index(neighbor)
            dist[i][j] = weight
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return {nodes[i]: {nodes[j]: dist[i][j] for j in range(n)} for i in range(n)}

# 示例图
graph = {
    'A': {'B': 3, 'C': 8},
    'B': {'D': 1},
    'C': {'B': 4},
    'D': {'A': 2, 'C': -5}
}

print(floyd_warshall(graph))
</syntaxhighlight>

==== 输出 ====
<pre>
{
    'A': {'A': 0, 'B': 3, 'C': 6, 'D': 4},
    'B': {'A': 3, 'B': 0, 'C': 3, 'D': 1},
    'C': {'A': 7, 'B': 4, 'C': 0, 'D': 5},
    'D': {'A': 2, 'B': -1, 'C': -5, 'D': 0}
}
</pre>

== 实际应用案例 ==
1. '''导航系统'''：计算两地之间的最短行驶路径（如Google Maps）。
2. '''网络路由'''：数据包在网络中选择最优路径传输（如OSPF协议）。
3. '''物流配送'''：优化货物运输路线以降低成本。

== 总结 ==
* Dijkstra算法适合非负权重图，时间复杂度为<math>O((V + E) \log V)</math>。
* Bellman-Ford算法可处理负权重，时间复杂度为<math>O(VE)</math>。
* Floyd-Warshall算法用于多源最短路径，时间复杂度为<math>O(V^3)</math>。

选择合适的算法取决于图的特性（如权重、稠密性）和问题需求（如单源或多源）。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]