"""在同一有向图上对照 Dijkstra 与 Bellman–Ford。运行:python mmf_shortest_path.py。""" import json # NumPy 操作小图距离表,Matplotlib 画有向边和最短路径。 import matplotlib.pyplot as plt import numpy as np def dijkstra(n, edges, source): # 无边用 Inf 表示,因此即使某条真实边的权为 0 也不会被忽略。 costs = np.full((n, n), np.inf) for start, end, weight in edges: if weight < 0: raise ValueError("Dijkstra 要求边权非负") costs[start, end] = weight # distance 是从起点出发的暂定代价,previous 为重建路径记录前驱。 # -1 表示尚未发现前驱,settled 追踪已经证明不能继续缩短的节点。 distance = np.full(n, np.inf) distance[source] = 0 previous = np.full(n, -1, dtype=int) settled = np.zeros(n, dtype=bool) order = [] for _ in range(n): # 非负边权保证最小待定距离可安全确定;剩余最小值为 Inf 意味着无法到达。 candidate = np.where(settled, np.inf, distance) nearest = int(np.argmin(candidate)) if not np.isfinite(candidate[nearest]): break settled[nearest] = True order.append(nearest) # 对所有未确定邻居执行松弛,布尔掩码只更新严格改善的条目。 new_distance = distance[nearest] + costs[nearest] improved = (~settled) & (new_distance < distance) distance[improved] = new_distance[improved] previous[improved] = nearest return distance, previous, order def bellman_ford(n, edges, source): distance = np.full(n, np.inf) distance[source] = 0 for _ in range(n - 1): # 每轮读取上一轮的距离,让第 k 轮恰好覆盖至多 k 条边的路径。 updated = distance.copy() for start, end, weight in edges: updated[end] = min(updated[end], distance[start] + weight) distance = updated # 没有可达负权环时,最优简单路径至多 n-1 条边,此后不应再出现严格改进。 if any(distance[start] + weight < distance[end] for start, end, weight in edges): raise ValueError("存在从起点可达的负权环") return distance def solve(n, edges): distance, previous, order = dijkstra(n, edges, source=0) np.testing.assert_allclose(distance, bellman_ford(n, edges, source=0)) target = n - 1 if not np.isfinite(distance[target]): raise ValueError("本实验需要起点到终点可达") # 从终点沿前驱逆走,反转后再把相邻两节点组成边,核算总代价。 route = [target] while route[-1] != 0: route.append(int(previous[route[-1]])) route.reverse() weights = {(u, v): w for u, v, w in edges} assert sum(weights[edge] for edge in zip(route, route[1:])) == distance[target] return distance, route, order def draw_graph(ax, edges, route, title): # 位置只决定绘图布局。真正参与计算的代价由边上数字表示,绿色突出选中的边。 positions = np.array([[0, 0], [1, 1], [1, -1], [2.4, 1], [2.4, -1], [3.5, 0]]) route_edges = set(zip(route, route[1:])) for u, v, weight in edges: start, end = positions[u], positions[v] selected = (u, v) in route_edges color = "tab:green" if selected else "0.55" ax.annotate("", xy=end, xytext=start, arrowprops={ "arrowstyle": "->", "color": color, "lw": 2 if selected else 1, "shrinkA": 12, "shrinkB": 12, }) mid = (start + end) / 2 ax.text(*mid, str(weight), ha="center", va="center", color=color, bbox={"facecolor": "white", "edgecolor": "none", "pad": 1}) ax.scatter(*positions.T, s=210, facecolors="white", edgecolors="0.3") for i, point in enumerate(positions): ax.text(*point, "ABCDEF"[i], va="center", ha="center") ax.set(title=title, xlim=(-0.35, 3.85), ylim=(-1.3, 1.3)) ax.set_aspect("equal") ax.axis("off") def main(): # 沿用网页动画中的校园通行网络。数组内部使用 0 开始的节点编号。 edges = [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 2)] # 只缩短 C 到 D 的通行时间,保留所有其他输入,比较路线会不会切换。 changed = [(u, v, 6 if (u, v) == (2, 3) else w) for u, v, w in edges] distance, route, order = solve(6, edges) changed_distance, changed_route, _ = solve(6, changed) # 输出时改为 1 起始节点号,让两份实验的路径和确定顺序能直接比较。 result = { "distances": distance.tolist(), "route": [idx + 1 for idx in route], "settle_order": [idx + 1 for idx in order], "changed_distances": changed_distance.tolist(), "changed_route": [idx + 1 for idx in changed_route], } print("LAB_RESULT " + json.dumps(result)) fig, (before, after) = plt.subplots(1, 2, figsize=(9, 3.8)) draw_graph(before, edges, route, f"Original route: {distance[-1]:g} min") draw_graph(after, changed, changed_route, f"C to D shortened: {changed_distance[-1]:g} min") fig.tight_layout() if plt.get_backend().lower() == "agg": fig.canvas.draw() else: plt.show() if __name__ == "__main__": main()