一、最短路径问题是什么？
想象你要从家到公司，有好多条路可以走，有的路堵车，有的路绕远。最短路径算法就是帮你在所有可能的路线中，快速找出最快、最省时间的那一条。在计算机世界里，这类问题无处不在，比如网络路由、物流配送、游戏AI寻路等。
二、Dijkstra算法：一步一步找最优解
Dijkstra算法的核心思想是“贪心”——每次只选当前看起来最好的那条路。它从起点出发，逐步探索周边节点，并记录到每个节点的最短距离，直到覆盖终点。
技术栈：Python
import heapq
def dijkstra(graph, start):
# 初始化：起点到自己的距离为0，其他节点为无穷大
distances = {node: float('inf') for node in graph}
distances[start] = 0
# 使用优先队列（堆）优化查找过程
queue = [(0, start)]
while queue:
current_dist, current_node = heapq.heappop(queue)
# 如果当前距离大于已记录的距离，跳过
if current_dist > distances[current_node]:
continue
# 遍历邻居节点
for neighbor, weight in graph[current_node].items():
distance = current_dist + weight
# 如果找到更短的路径，更新并加入队列
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# 示例图（字典表示，键是节点，值是该节点到邻居的权重）
graph = {
'A': {'B': 2, 'C': 5},
'B': {'A': 2, 'C': 1, 'D': 3},
'C': {'A': 5, 'B': 1, 'D': 2},
'D': {'B': 3, 'C': 2}
}
print(dijkstra(graph, 'A')) # 输出：{'A': 0, 'B': 2, 'C': 3, 'D': 5}
注释说明：
heapq是Python的优先队列模块，帮助快速找到当前最短路径的节点。distances字典记录从起点到每个节点的最短距离，初始时为无穷大（inf）。- 每次从队列中取出距离最小的节点，并更新其邻居的距离。
适用场景：
- 导航系统中计算单源最短路径（比如从你家到所有附近商场的路线）。
- 要求图中不能有负权边（比如“倒贴钱”的路，Dijkstra无法处理）。
三、Floyd-Warshall算法：全盘考虑所有可能性
如果Dijkstra是“一步步探索”，Floyd-Warshall就是“全局统筹”。它通过动态规划的思想，计算图中所有节点之间的最短路径。
技术栈：Python
def floyd_warshall(graph):
# 初始化距离矩阵
nodes = list(graph.keys())
n = len(nodes)
dist = [[float('inf')] * n for _ in range(n)]
# 设置对角线为0（自己到自己的距离）
for i in range(n):
dist[i][i] = 0
# 填充初始边权重
for i, u in enumerate(nodes):
for j, v in enumerate(nodes):
if v in graph[u]:
dist[i][j] = graph[u][v]
# 动态规划核心：三重循环更新距离
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)}
# 示例图（与Dijkstra相同）
graph = {
'A': {'B': 2, 'C': 5},
'B': {'A': 2, 'C': 1, 'D': 3},
'C': {'A': 5, 'B': 1, 'D': 2},
'D': {'B': 3, 'C': 2}
}
print(floyd_warshall(graph))
注释说明：
dist是一个二维数组，保存所有节点之间的最短距离。- 三重循环中，
k是“中转节点”，检查是否通过k能让i到j的路径更短。
适用场景：
- 需要计算所有节点之间的最短路径（比如城市交通规划）。
- 能处理负权边（但不能有负权环，否则会陷入无限循环）。
四、导航系统中的实际应用
Dijkstra的典型场景：
- 手机导航App中，输入起点和终点后，实时计算一条最短路径。
- 优点：速度快，适合稀疏图（边少的场景）。
- 缺点：无法处理负权边，且每次只能计算单源路径。
Floyd-Warshall的典型场景：
- 预计算所有城市之间的最短路径，存储在服务器中供快速查询。
- 优点：一次计算，多次查询；支持负权边。
- 缺点：时间复杂度高（O(n³)），不适合大规模图。
注意事项：
- Dijkstra优先用堆优化（如Python的
heapq），否则性能会下降。 - Floyd-Warshall的空间复杂度是O(n²)，对于超大规模图需谨慎使用。
五、总结
- 简单需求选Dijkstra：比如导航App的实时路径计算。
- 复杂需求选Floyd-Warshall：比如物流公司需要全局路径规划。
- 两者互补，实际系统中可能结合使用（比如先用Floyd预处理核心节点，再用Dijkstra细化）。
评论