网络延迟时间与路径重建
使用 Dijkstra 算法解决网络延迟时间问题，通过前驱映射重建实际最短路径，并讨论适用于大型图的双向 BFS。
网络延迟时间与路径重建 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
网络延迟时间问题
网络延迟时间（LeetCode 743）：给定一个包含 n 个节点的网络，以及表示信号传输时间的有向带权边，请求出从节点 k 发送的信号到达所有节点所需的最短时间。如果某个节点无法到达，则返回 -1。这是迪杰斯特拉算法的直接应用：答案就是从 k 出发到所有节点的最短路径距离中的最大值。
解法：迪杰斯特拉算法与距离最大值
请从源节点 k 运行迪杰斯特拉算法，求出所有节点 v 的 dist[v]。答案是 max(dist.values())。如果某个 dist[v] 仍为 inf，则表示该节点无法到达，请返回 -1。信号会同时沿所有路径传播，因此瓶颈是到达时间最长的节点。
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
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)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2使用前驱数组重建路径
如果需要在计算距离的同时重建实际的最短路径，请维护一个前驱字典，记录每个节点的最佳前驱节点。每当更新 dist[v] 时，请设置 prev[v] = u。迪杰斯特拉算法完成后，从目标节点开始沿着前驱指针反向追溯，直到到达源节点，然后将结果反转以得到正向路径。
import heapq
from collections import defaultdict
def shortest_path_with_reconstruction(times, n, src, dst):
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)}
prev = {i: None for i in range(1, n+1)}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct path from src to dst
path, node = [], dst
while node is not None:
path.append(node)
node = prev[node]
return dist[dst], path[::-1]大型无权图的双向 BFS
对于只需要求一个源节点到目标节点的路径、且规模较大的无权图，双向 BFS 的速度可能明显快于标准 BFS。它会同时从源节点和目标节点运行 BFS，并在两个搜索前沿相遇时停止。实际加速效果很明显，因为每个搜索前沿只需探索一半的图深度——将探索的节点数从 O(b^d) 降低到 O(2 × b^(d/2))，其中 b 是分支因子。
from collections import deque
def bidir_bfs(graph, src, dst):
if src == dst: return 0
front_q = deque([src]); front_visited = {src: 0}
back_q = deque([dst]); back_visited = {dst: 0}
def expand(queue, visited, other_visited):
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited[nxt] = visited[node] + 1
queue.append(nxt)
if nxt in other_visited:
return visited[nxt] + other_visited[nxt]
return -1
while front_q or back_q:
res = expand(front_q, front_visited, back_visited)
if res != -1: return res
res = expand(back_q, back_visited, front_visited)
if res != -1: return res
return -1如何选择算法
决策指南：无权图，单个点对 → BFS 或双向 BFS。带权、非负权重、单源 → 迪杰斯特拉算法。带权、可能存在负权重、单源 → 贝尔曼-福特算法。所有点对 → 弗洛伊德-沃舍尔算法（V 较小）或 V × 迪杰斯特拉算法（图较稀疏）。有限跳数 → 限制遍数的改进版贝尔曼-福特算法。在面试中大声说明这一决策依据，可以体现您的算法素养。
可达邻居最少的城市（LeetCode 1334）
给定若干城市及其带权路径，以及一个 distanceThreshold，请找出在该阈值内可到达的其他城市数量最少的城市（如果数量相同，则优先选择城市编号较大的城市）。解法：使用弗洛伊德-沃舍尔算法计算所有点对之间的最短路径，然后统计每个城市在该阈值内可以到达的其他城市数量。返回数量最少的城市（数量相同时返回编号最大的城市）。
def findTheCity(n, edges, distanceThreshold):
INF = float('inf')
dist = [[INF]*n for _ in range(n)]
for i in range(n): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = dist[v][u] = w
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])
best_city, best_count = -1, n
for city in range(n):
count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
if count <= best_count:
best_count = count
best_city = city
return best_city
print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4)) # 3带权 DAG 中的路径
对于有向无环图（DAG），可以通过拓扑排序和松弛在 O(V+E) 时间内求出最短路径（或最长路径），速度快于迪杰斯特拉算法。请按照拓扑顺序处理节点；处理节点 u 时，松弛所有出边。对于最长路径（可用于项目调度或关键路径），可以将权重取反，或者将 min 改为 max。
from collections import deque
def dag_shortest_path(V, edges, source):
graph = [[] for _ in range(V)]
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
# Topological sort (Kahn's)
queue = deque(i for i in range(V) if in_degree[i] == 0)
topo = []
while queue:
node = queue.popleft(); topo.append(node)
for nxt, _ in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
# Relax in topological order
dist = [float('inf')] * V
dist[source] = 0
for u in topo:
if dist[u] != float('inf'):
for v, w in graph[u]:
dist[v] = min(dist[v], dist[u] + w)
return dist带障碍物矩阵中的最短路径
一种常见的面试题变体是：在一个二维网格中，从左上角找到通往右下角的最短路径，其中部分单元格可能被阻塞。这是一个无权 BFS 问题（每一步的代价都是 1）。请使用四个方向移动的 BFS，并在单元格入队时（而不是出队时）将其标记为已访问，以避免重复访问。如果可以带代价穿过障碍物，请在二维网格上使用迪杰斯特拉算法，将网格视为带权图。
from collections import deque
def shortest_path_binary_matrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
visited = {(0, 0)}
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while queue:
r, c, d = queue.popleft()
if r == n-1 and c == n-1:
return d
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
visited.add((nr,nc))
queue.append((nr, nc, d+1))
return -1
print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]])) # 4多源 BFS
当存在多个起点时（例如网格中的多个“入口”、地图中的多个起源点），请运行多源 BFS：同时将所有源节点以距离 0 入队。这样只需进行一次 BFS 遍历，就可以计算每个单元格到最近源节点的最短距离。这种技术避免了分别从每个源节点运行 BFS，总时间复杂度为 O(V+E)。
算法选择回顾
简明决策树：单源、非负权重 → 迪杰斯特拉算法 O((V+E) log V)。单源、负权重 → 贝尔曼-福特算法 O(VE)。所有点对、V 较小 → 弗洛伊德-沃舍尔算法 O(V³)。DAG、任意权重 → 拓扑排序 + 松弛 O(V+E)。无权图 → BFS O(V+E)。网格路径 → BFS（无权）或使用堆的迪杰斯特拉算法（带权）。请记住这张表——它可以帮助您回答任何最短路径面试中的追问。
面试题中的路径查找
许多面试题要求返回实际路径，而不仅仅是代价。请始终确认：您需要路径，还是只需要距离？如果需要路径，请从一开始就分配一个 prev 字典。常见错误包括：忘记将 prev[source] = None 初始化为终止条件，以及混淆重建顺序（从目标节点追溯到源节点，然后反转）。在应用到更大的问题之前，请先用包含 3～4 个节点的示例练习路径重建。
快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学到了：运行迪杰斯特拉算法后，网络延迟时间的答案是 max(dist.values())；路径重建通过在 dist[v] 改善时更新前驱数组来完成；以及对于单个点对的无权最短路径，双向 BFS 可以将搜索空间缩小一半。接下来，我们将通过卡恩算法学习图排序和拓扑排序。
常见问题解答
「网络延迟时间与路径重建」课时是免费的吗？
是的 — 「网络延迟时间与路径重建」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「网络延迟时间与路径重建」这节课中我会学到什么？
使用 Dijkstra 算法解决网络延迟时间问题，通过前驱映射重建实际最短路径，并讨论适用于大型图的双向 BFS。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「网络延迟时间与路径重建」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。