导航软件的核心算法，从一点到另一点的最优路径选择
最短路径问题是图论中最经典的问题之一：在加权图中，找到两个顶点之间权值之和最小的路径。不同的约束条件（边权正/负、单源/全源、限制中转次数）催生了不同的算法。
import heapq
from collections import defaultdict
def dijkstra(n, edges, start):
"""单源最短路 - Dijkstra
n: 顶点数, edges: [(u, v, w), ...], start: 起点
返回: dist 数组
"""
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)] # (距离, 节点)
visited = set()
while heap:
d, node = heapq.heappop(heap)
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distO((V+E)log V)。不使用堆的朴素版本为 O(V²)，在稠密图（E ≈ V²）时朴素版更快。面试一般用堆优化版。题目描述：有 n 个网络节点，标记为 1 到 n。给定列表 times，表示信号经过边的传播时间 [u, v, w]。从节点 k 发出信号，多久才能使所有节点都收到信号？如果不能使所有节点收到，返回 -1。
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
import heapq
from collections import defaultdict
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n + 1)}
dist[k] = 0
heap = [(0, k)]
visited = set()
while heap:
d, node = heapq.heappop(heap)
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph[node]:
if d + weight < dist[neighbor]:
dist[neighbor] = d + weight
heapq.heappush(heap, (dist[neighbor], neighbor))
return max(dist.values()) if len(visited) == n else -1时间复杂度：O((V+E)log V)
空间复杂度：O(V+E)
题目描述：有 n 个城市通过航班连接，flights[i] = [from, to, price]。找到从 src 到 dst 最多经过 k 站中转的最便宜价格。如果没有路线，返回 -1。
(cost, node, stops)。当 stops > k 时跳过。best[(node, stops)] 记录到达某节点用了某站数的最小花费，避免重复扩展。
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]],
src: int, dst: int, k: int) -> int:
import heapq
from collections import defaultdict
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w))
heap = [(0, src, 0)] # (cost, node, stops)
best = {} # (node, stops) → min cost
while heap:
cost, node, stops = heapq.heappop(heap)
if node == dst:
return cost
if stops > k:
continue
key = (node, stops)
if key in best and best[key] <= cost:
continue
best[key] = cost
for neighbor, price in graph[node]:
heapq.heappush(heap, (cost + price, neighbor, stops + 1))
return -1时间复杂度：O(E·K·log(E·K))
空间复杂度：O(V·K)
题目描述：给你一个无向加权图，边的权重是成功概率。求从 start 到 end 的最大概率路径的概率值。
prob[u] * w > prob[v]，更新 prob[v]class Solution:
def maxProbability(self, n: int, edges: List[List[int]],
succProb: List[float], start: int, end: int) -> float:
import heapq
from collections import defaultdict
graph = defaultdict(list)
for (u, v), p in zip(edges, succProb):
graph[u].append((v, p))
graph[v].append((u, p))
prob = [0.0] * n
prob[start] = 1.0
heap = [(-1.0, start)] # 负值模拟最大堆
while heap:
p, node = heapq.heappop(heap)
p = -p
if p < prob[node]: # 已过期
continue
for neighbor, w in graph[node]:
if p * w > prob[neighbor]:
prob[neighbor] = p * w
heapq.heappush(heap, (-prob[neighbor], neighbor))
return prob[end]时间复杂度：O((V+E)log V)
空间复杂度：O(V+E)
| 算法 | 适用图 | 时间复杂度 | 特点 |
|---|---|---|---|
| BFS | 无权图 | O(V+E) | 最简单，层序扩展 |
| Dijkstra | 非负权图 | O((V+E)logV) | 单源最短路，贪心 |
| Bellman-Ford | 可有负权 | O(VE) | 可检测负权环 |
| SPFA | 可有负权 | 平均O(V+E) | BF的队列优化 |
| Floyd-Warshall | 全源最短路 | O(V³) | 三重循环，适合小图 |
| A* | 有启发函数 | 取决于启发 | 目标导向搜索 |
# 全源最短路 - Floyd-Warshall
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 直觉: i → j 的最短路是否经过 k?
# 枚举所有中间点 k, 逐步更新