主题
最短路径:Dijkstra 与图搜索
方法速览
- 主要用途 在加权图中求两点(或单源到所有点)的最短路径与距离,用于路线规划、网络距离、配送路径等。
- 必要输入 节点集合、带权的边(每条边有权值,Dijkstra 要求权值非负)、起点(与终点)。
- 适用条件 图静态且边权已知;Dijkstra 要求边权非负;路径成本可加(总成本 = 各边权之和)。
- 典型不适用情况 含负权边(改用 Bellman-Ford 或 Floyd);每条边有容量上限的流量问题(用最大流);要遍历所有点的回路(用 TSP);动态/时变网络。
- 最低限度的验证方式 与 Bellman-Ford / Floyd 在小图上对照;把最短路径各边权累加核对是否等于报告距离;手算一个小图。
快速回答
Dijkstra 是单源最短路径的贪心算法:维护「距离表 + 前驱表 + 已确定集合」,每轮从尚未确定的节点中取距离最小者加入已确定集合,再松弛它的出边——即用「已确定节点的最短距离 + 边权」去尝试缩短邻居的距离表。它的正确性依赖「边权非负」:一个节点一旦被确定,它的最短距离就是最终值,不会再被更新。负权会破坏这一点:反例 A→B=2、A→C=3、C→B=−2 中,Dijkstra 停在 B 距离 2,而真实最短是 A→C→B = 3+(−2) = 1。不可达节点距离记
从零理解
想象你在校园里,从宿舍 A 走到体育馆 F,想知道怎么走最省时间。先把地图抽象成一张带权网络:每个路口是一个节点,每条路是一条有向边,边权就是通行时间(或距离)。几何上「A 离 B 近不近」不重要,重要的是边权——因为 A、B 之间可能隔着一堵墙,直线很近却走不通。
Dijkstra 的思路很像「从起点一圈圈往外扩展」:先确定起点距离为 0;然后不断重复「在还没确定的点里,挑一个目前看起来最近的点,把它锁定,再看从它出发能顺路走多远」。所谓「确定」就是「这个点的最短距离已经算死了,后面不用再改」。只要所有边权都非负,「当前最近的未确定点」就必然是全局最近的点——因为它不可能再被任何「更远的点 + 一条非负权重边」抄近路追上。这就是贪心的依据,也正是负权会翻车的根源。
数学原理
符号定义
| 符号 | 含义 |
|---|---|
| 有向带权图, | |
| 边 | |
| 源点(起点) | |
| 起点到 | |
| 已确定集合(已入集节点的 |
Dijkstra:贪心 + 松弛
初始化
- 选最小:在
中选 最小的节点 ,加入 (此时 的最短距离确定)。 - 松弛:对每条出边
( ),若 则更新 并记 。
最后从终点沿
为什么负权会让 Dijkstra 失效
设三条边:
- Dijkstra 第 1 步确定
,松弛得 、 。 - 第 2 步在
与 中选更小的 ,立即把 锁定为 2。 - 但真实最短是
。Dijkstra 因负权「贪心锁定」而过早定格,给出错误答案。
结论:只要图里存在负权边,就不能用 Dijkstra(本文实现会直接抛错),应改用 Bellman-Ford(可处理负权、检测负权环)或 Floyd-Warshall。
复杂度
| 算法 | 场景 | 时间复杂度 | 空间复杂度 | 负权 |
|---|---|---|---|---|
| Dijkstra(O(V²) 扫描) | 单源,非负权 | 不支持 | ||
| Dijkstra(二叉堆) | 单源,非负权 | 不支持 | ||
| Bellman-Ford | 单源,可负权 | 支持,检测负权环 | ||
| Floyd-Warshall | 全源,可负权 | 支持,检测负权环 | ||
| A* | 单源到单点,需启发函数 | 取决于启发式 | 不支持(需 |
动态实验
距离表(节点 → 距离,未达为 —)
| A | 0 |
|---|---|
| B | 4 |
| C | 2 |
| D | — |
| E | — |
| F | — |
已确定集合
A
当前选中
A
从距离表选最小未确定节点 A(距离 0),松弛出边 A→B(4)、A→C(2),更新距离表。
1 / 6
参数说明:
- 起点 / 终点:下拉选择;默认 A→F(非负权示例图)。
- 示例:负权图:勾选后切换到 3 节点负权图 A→B=2、A→C=3、C→B=−2,演示 Bellman-Ford 并显示负权警告(此时 Dijkstra 不适用)。
动画的每一帧都对应算法真实的一次迭代:Dijkstra 模式下是「从距离表选最小未确定节点 + 松弛其出边」,与 applyStepTrace 的帧数组逐一对应,末帧距离表与一次性 dijkstra 结果完全一致(跳帧同态);负权图模式切换为 Bellman-Ford,每帧 = 一轮「松弛所有边」。下表为非负权示例图从 A 出发的完整手算过程(
| 轮次 | 确定节点 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 初始 | — | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | A | 0 | 4 | 2 | ∞ | ∞ | ∞ |
| 2 | C | 0 | 4 | 2 | 10 | 12 | ∞ |
| 3 | B | 0 | 4 | 2 | 9 | 12 | ∞ |
| 4 | D | 0 | 4 | 2 | 9 | 11 | 15 |
| 5 | E | 0 | 4 | 2 | 9 | 11 | 13 |
| 6 | F | 0 | 4 | 2 | 9 | 11 | 13 |
最短路径 A→F = A → B → D → E → F,距离 13。候选路径 A→C→D→E→F=14、A→C→E→F=14、A→B→D→F=15 均不更短。
先判断任务范围
如果只求一个起点到一个终点,给定的边权非负时可用 Dijkstra。若有固定起点且需要到所有终点的距离,可以用同一次完整扫描。若能绕行可达负权环后抵达目标,路径成本沿环继续降低,目标就没有有限最短距离。路径规划若还要求一辆车顺序访问多个站点,则要另外确定访问顺序,单次最短路只能提供站点间的成本。
代码实践
完整代码
下面直接展示仓库中的 examples/shortest_path.py,可用 python examples/shortest_path.py 直接运行。脚本用 heapq 版 Dijkstra 与 Bellman-Ford 互相核对,断言与前端 TS 引擎(tests/shortest-path.test.ts)钉死的路径/距离一致,并生成节点+边权+最短路径高亮图。
py
# -*- coding: utf-8 -*-
"""最短路径(Dijkstra 与 Bellman-Ford)—— MathModel FAQ 可运行算例。
图(6 节点 A–F,有向,边权非负):
A→B=4, A→C=2, B→C=1, B→D=5, C→D=8, C→E=10, D→E=2, D→F=6, E→F=2
手算结果(Dijkstra,节点确定顺序 A→C→B→D→E→F):
A→F 最短路径 = A → B → D → E → F,总距离 4+5+2+2 = 13。
其它候选:A→C→D→E→F=14、A→C→E→F=14、A→B→D→F=15、A→C→D→F=16,均 ≥13。
负权图(3 节点,Bellman-Ford 对照):A→B=2, A→C=3, C→B=−2。
Dijkstra 贪心会误判 A→B=2;真实最短 A→C→B = 3+(−2) = 1。
验证矩阵:
1. heapq 版 Dijkstra(独立实现)
2. Bellman-Ford(可处理负权、检测负权环)
两者在非负权图上 dist 与 prev 逐点一致;负权图 Dijkstra 抛错、Bellman-Ford 得正确路径。
数值与 tests/shortest-path.test.ts 钉死的路径/距离逐位一致。
运行方式(本机实测:Python 3.14.8 + numpy 2.5.3 + matplotlib 3.11.2):
python examples/shortest_path.py
输出:控制台逐步松弛日志 + 数值表
+ docs/public/examples/shortest-path-demo.png(节点+边权+最短路径高亮)。
"""
# 最小堆每次弹出最小暂定距离,适合用邻接表扫描稀疏图。
import heapq
import math
import sys
from pathlib import Path
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import numpy as np
plt.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei']
plt.rcParams['axes.unicode_minus'] = False
ROOT = Path(__file__).resolve().parent.parent
OUT_DIR = ROOT / 'docs' / 'public' / 'examples'
INF = float('inf')
NODES = ['A', 'B', 'C', 'D', 'E', 'F']
EDGES = [
('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5),
('C', 'D', 8), ('C', 'E', 10), ('D', 'E', 2), ('D', 'F', 6), ('E', 'F', 2)
]
NEG_NODES = ['A', 'B', 'C']
NEG_EDGES = [('A', 'B', 2), ('A', 'C', 3), ('C', 'B', -2)]
# 绘图坐标(与前端组件同一布局,y 向上)
POS = {
'A': (60, 180), 'B': (200, 270), 'C': (200, 90),
'D': (360, 270), 'E': (360, 90), 'F': (520, 180)
}
WEIGHT = {(f, t): w for f, t, w in EDGES}
SHORTEST_EDGES = {('A', 'B'), ('B', 'D'), ('D', 'E'), ('E', 'F')}
def dijkstra(nodes, edges, source):
"""heapq 版 Dijkstra;负权边直接抛错(与 TS 引擎口径一致)。"""
if any(w < 0 for _, _, w in edges):
bad = next((f, t, w) for f, t, w in edges if w < 0)
raise ValueError(
f'Dijkstra 要求所有边权非负,但边 {bad[0]}→{bad[1]} 的权为 {bad[2]}'
'(含负权请改用 Bellman-Ford)'
)
# 有向邻接表只存出边;dist 和 prev 分别记录暂定距离和前驱。
adj = {n: [] for n in nodes}
for f, t, w in edges:
adj[f].append((t, w))
dist = {n: INF for n in nodes}
prev = {n: None for n in nodes}
dist[source] = 0
pq = [(0.0, source)]
settled = set()
trace = [] # (node, dist_snapshot, [(to, new_dist), ...])
while pq:
d, u = heapq.heappop(pq)
# 堆中允许保留历史距离。弹出时跳过已确定节点和被更短距离替换的旧条目。
if u in settled or d != dist[u]:
continue
settled.add(u)
updates = []
for t, w in adj[u]:
if t in settled:
continue
# 松弛同时更新距离和前驱,严格小于才替换已发现的等长路线。
nd = d + w
if nd < dist[t]:
dist[t] = nd
prev[t] = u
heapq.heappush(pq, (nd, t))
updates.append((t, nd))
# 存一份距离字典副本,后续松弛不会改写先前帧。
trace.append((u, dict(dist), updates))
return dist, prev, trace
def bellman_ford(nodes, edges, source):
"""Bellman-Ford;可处理负权,检测负权环。"""
dist = {n: INF for n in nodes}
prev = {n: None for n in nodes}
dist[source] = 0
v = len(nodes)
for _ in range(v - 1):
# 原地松弛,距离可能在本轮被多条边连续改进;无改进即可提早停止。
changed = False
for f, t, w in edges:
if dist[f] == INF:
continue
nd = dist[f] + w
if nd < dist[t]:
dist[t] = nd
prev[t] = f
changed = True
if not changed:
break
# 第 v 轮若还能从可达节点缩短距离,说明存在起点可达的负权环。
for f, t, w in edges:
if dist[f] != INF and dist[f] + w < dist[t]:
raise ValueError('图中存在负权环,最短路径无定义(距离可无限变小)')
return dist, prev
def reconstruct(prev, target):
"""从前驱表回溯 source→target 路径。"""
path = []
cur = target
seen = set()
while cur is not None:
# 正常前驱链止于起点的 None。seen 避免异常前驱表让回溯一直循环。
if cur in seen:
break
seen.add(cur)
path.append(cur)
cur = prev[cur]
path.reverse()
return path
def check_dijkstra():
print('== Dijkstra(heapq)与 Bellman-Ford 在非负权图上 ==')
dist, prev, trace = dijkstra(NODES, EDGES, 'A')
expected = {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 11, 'F': 13}
assert dist == expected, f'Dijkstra 距离表 {dist} 与手算 {expected} 不一致'
settle_order = [u for u, _, _ in trace]
assert settle_order == ['A', 'C', 'B', 'D', 'E', 'F'], f'确定顺序 {settle_order} 与手算不符'
path = reconstruct(prev, 'F')
assert path == ['A', 'B', 'D', 'E', 'F'] and dist['F'] == 13, f'最短路径 {path} / {dist["F"]} 与手算不符'
bf_dist, bf_prev = bellman_ford(NODES, EDGES, 'A')
assert bf_dist == dist, 'Bellman-Ford 与 Dijkstra 距离表不一致'
assert bf_prev == prev, 'Bellman-Ford 与 Dijkstra 前驱表不一致'
print(' Dijkstra 节点确定顺序:', ' → '.join(settle_order))
print(' 最短路径 A→F =', ' → '.join(path), ',距离 =', dist['F'])
print(' Bellman-Ford 与 Dijkstra 在非负权图上 dist/prev 逐点一致。')
print()
print('== 逐步松弛日志(每帧 = 一次「确定最小节点 + 松弛其邻边」)==')
for u, snapshot, updates in trace:
if updates:
parts = ';'.join(f'{u}→{t}={WEIGHT.get((u, t), "?")} → {t}:{nd}' for t, nd in updates)
print(f' 确定 {u}(距离 {snapshot[u]}):松弛 {parts}')
else:
print(f' 确定 {u}(距离 {snapshot[u]}):无出边(或目标已确定)')
if u == 'F':
print(' 已确定目标 F,停止。')
return dist, path
def check_negative():
print()
print('== 负权图对照 ==')
try:
dijkstra(NEG_NODES, NEG_EDGES, 'A')
raise AssertionError('负权图应触发 Dijkstra 抛错')
except ValueError as err:
print(f' Dijkstra 负权抛错:{err}')
dist, prev = bellman_ford(NEG_NODES, NEG_EDGES, 'A')
assert dist['B'] == 1 and dist['C'] == 3, f'Bellman-Ford 负权图距离 {dist} 与手算不符'
path = reconstruct(prev, 'B')
assert path == ['A', 'C', 'B'], f'Bellman-Ford 负权路径 {path} 与手算不符'
print(f' Bellman-Ford 最短路径 A→B = {" → ".join(path)},距离 = {dist["B"]}(Dijkstra 会误判为 2)')
return dist, path
def check_negative_cycle():
print()
print('== 负权环检测 ==')
nodes = ['A', 'B', 'C']
edges = [('A', 'B', 1), ('B', 'C', 1), ('C', 'B', -2)]
try:
bellman_ford(nodes, edges, 'A')
raise AssertionError('存在负权环时应抛错')
except ValueError as err:
print(f' 检测到负权环并抛错:{err}')
def make_figure(path):
OUT_DIR.mkdir(parents=True, exist_ok=True)
fig, ax = plt.subplots(figsize=(7.6, 4.6), dpi=110)
def mid_offset(f, t, dist_px=15):
# 权重放在线段中点的侧面,避免文字被有向箭头遮住。
(xf, yf), (xt, yt) = POS[f], POS[t]
dx, dy = xt - xf, yt - yf
length = math.hypot(dx, dy) or 1.0
px, py = -dy / length, dx / length
return (xf + xt) / 2 + px * dist_px, (yf + yt) / 2 + py * dist_px
# 原图的已核对路径用绿边标出。坐标只用于展示,路径权重来自边表。
for f, t, _ in EDGES:
is_short = (f, t) in SHORTEST_EDGES
color = '#1f8a4c' if is_short else '#b0b6c0'
lw = 2.6 if is_short else 1.2
(xf, yf), (xt, yt) = POS[f], POS[t]
ax.annotate('', xy=(xt, yt), xytext=(xf, yf),
arrowprops=dict(arrowstyle='-|>', color=color, lw=lw,
shrinkA=20, shrinkB=20, mutation_scale=14))
mx, my = mid_offset(f, t)
ax.text(mx, my, str(WEIGHT[(f, t)]), ha='center', va='center', fontsize=10,
color='#1f8a4c' if is_short else '#555b66',
bbox=dict(boxstyle='round,pad=0.15', fc='white', ec='none', alpha=0.85))
for node, (x, y) in POS.items():
is_src, is_dst = node == 'A', node == 'F'
fc = '#5d42bc' if is_src else ('#1f8a4c' if is_dst else '#ecebf6')
ec = '#5d42bc' if (is_src or is_dst) else '#b0b6c0'
ax.scatter([x], [y], s=680, c=[fc], edgecolors=[ec], linewidths=1.6, zorder=3)
ax.text(x, y, node, ha='center', va='center', fontsize=12, fontweight='bold',
color='#ffffff' if (is_src or is_dst) else '#2b2b3a', zorder=4)
ax.set_xlim(0, 620)
ax.set_ylim(40, 330)
ax.set_aspect('equal')
ax.axis('off')
ax.set_title('最短路径 A→F:' + ' → '.join(path) + ' = 13(绿色边为最短路径链)', fontsize=11)
fig.tight_layout()
out = OUT_DIR / 'shortest-path-demo.png'
fig.savefig(out)
plt.close(fig)
print(f'== 绘图已保存到 {out} ==')
def main() -> None:
print('== 环境 ==')
print(f' Python {sys.version.split()[0]}')
import numpy as _np, matplotlib as _mpl
print(f' numpy {_np.__version__}, matplotlib {_mpl.__version__}')
dist, path = check_dijkstra()
check_negative()
check_negative_cycle()
make_figure(path)
print('== 全部断言通过 ==')
if __name__ == '__main__':
main()运行方式
bash
cd mathmodel-faq
pip install numpy matplotlib # 本算例仅需 numpy + matplotlib
python examples/shortest_path.py本机实测环境:Python 3.14.8、numpy 2.5.3、matplotlib 3.11.2。脚本不联网、不依赖网络库;所有断言失败时以非零退出码退出。
输出结果(本机实际运行)
text
== 环境 ==
Python 3.14.8
numpy 2.5.3, matplotlib 3.11.2
== Dijkstra(heapq)与 Bellman-Ford 在非负权图上 ==
Dijkstra 节点确定顺序: A → C → B → D → E → F
最短路径 A→F = A → B → D → E → F ,距离 = 13.0
Bellman-Ford 与 Dijkstra 在非负权图上 dist/prev 逐点一致。
== 逐步松弛日志(每帧 = 一次「确定最小节点 + 松弛其邻边」)==
确定 A(距离 0):松弛 A→B=4 → B:4.0;A→C=2 → C:2.0
确定 C(距离 2.0):松弛 C→D=8 → D:10.0;C→E=10 → E:12.0
确定 B(距离 4.0):松弛 B→D=5 → D:9.0
确定 D(距离 9.0):松弛 D→E=2 → E:11.0;D→F=6 → F:15.0
确定 E(距离 11.0):松弛 E→F=2 → F:13.0
确定 F(距离 13.0):无出边(或目标已确定)
已确定目标 F,停止。
== 负权图对照 ==
Dijkstra 负权抛错:Dijkstra 要求所有边权非负,但边 C→B 的权为 -2(含负权请改用 Bellman-Ford)
Bellman-Ford 最短路径 A→B = A → C → B,距离 = 1(Dijkstra 会误判为 2)
== 负权环检测 ==
检测到负权环并抛错:图中存在负权环,最短路径无定义(距离可无限变小)
== 绘图已保存到 …docs\public\examples\shortest-path-demo.png ==
== 全部断言通过 ==结果图

关键参数
| 参数 | 含义 | 本算例取值与效果 |
|---|---|---|
| nodes / edges | 图结构 | 6 节点 A–F、9 条有向边;边权固定,无随机性 |
| source / target | 起点 / 终点 | 默认 A→F,距离 13,路径 A→B→D→E→F |
| w | 边权 | 非负时用 Dijkstra;出现负权必须切 Bellman-Ford / Floyd |
| heapq 优先队列 | Dijkstra 的「选最小」数据结构 | 本算例用 heapq 实现 O((V+E)log V),前端用 O(V²) 扫描教学版 |
常见错误
- 负权边仍用 Dijkstra:Dijkstra 贪心会过早锁定节点,得到错误答案(如 A→B 被误判为 2)。负权应改用 Bellman-Ford 或 Floyd,并检测负权环。
- 边权单位不一致:有的边按距离、有的按时间、有的按费用混在一起相加,得到的「最短」无意义。先把所有边换算到同一量纲(见单位与符号写错会怎样?)。
- 把欧氏距离当实际路线:地图上两点直线很近,但可能没有直连道路;最短路径应基于真实路网边权,而不是节点坐标的欧氏距离。
- 忽略不可达(不连通):不连通点对距离为
,没有路径;代码应返回「不可达」而不是硬造一条路径或给出 0。
专业速查
| 项目 | 内容 |
|---|---|
| 假设 | 图为静态、边权已知;Dijkstra 要求边权非负;路径成本可加 |
| 参数 | 节点集 |
| 复杂度 | Dijkstra:O(V²) 扫描或 O((V+E)log V) 堆;Bellman-Ford:O(VE);Floyd:O(V³) |
| 优点 | 简单直观、可手算可编程;非负权下高效且正确;前驱表能回溯完整路径 |
| 缺点 | Dijkstra 不能处理负权;稠密图效率低于 Floyd;大规模地图需专用算法(A*、分层图) |
| 评价指标 | 最短距离、路径序列、与 Bellman-Ford/Floyd 对照一致性、路径各边权累加等于报告距离 |
| 相关 FAQ | 单位与符号写错会怎样?、如何检查模型结果是否可靠 |
双语言实验
通行时间一变,应该改走哪条路
沿用上面动画的六节点校园图,将边权理解为教学设定的通行分钟数。原图从 A 经 B 到 D 用
代码用邻接矩阵演示 Dijkstra,矩阵用
每轮只读上轮距离,恰好对应多允许一条边。若无可达负权环,可删除重复节点之间的非负代价环,故至少有一条最短路至多用
独立运行
Python 在终端安装依赖 python -m pip install numpy matplotlib,下载文件后运行 python mmf_shortest_path.py。MATLAB 将 mmf_shortest_path.m 放入当前文件夹,在命令窗口运行 result = mmf_shortest_path(),基础实验无需额外工具箱。两种脚本均输出数值并绘制图形。
手写非负有向图的选点与松弛,检查从 1 号结点到其余点的距离为 0、2、1、4。例子含不可达结点,算法及时停止。
最简版依赖 Python:无第三方依赖。MATLAB:基础功能,无需额外工具箱。
在源码所在目录运行 python mmf_min_shortest_path.py
py
下载当前源码import json
graph = [[(1, 4), (2, 1)], [(3, 2)], [(1, 1), (3, 5)], [], []]
distance = [0] + [float("inf")] * (len(graph) - 1)
unvisited = list(range(len(graph)))
while unvisited:
# 距离最小者先定型。非负边保证已定型距离不会被后续路径改善。
node = min(unvisited, key=lambda index: distance[index])
if distance[node] == float("inf"):
break
unvisited.remove(node)
for neighbor, weight in graph[node]:
distance[neighbor] = min(distance[neighbor], distance[node] + weight)
assert distance[:4] == [0, 2, 1, 4] and unvisited == [4]
result = {"reachable_distances": distance[:4], "unreachable_count": len(unvisited)}
print("LAB_RESULT " + json.dumps(result, ensure_ascii=False))NumPy 用以 0 开始的位置索引边,MATLAB 通过 sub2ind 将边端点转成矩阵的线性下标。两种语言都输出从 1 开始的节点编号,对应 A 到 F。distances 应为 [0,4,2,9,11,13],settle_order 为 [1,3,2,4,5,6],改动后 changed_route 应为 [1,3,4,5,6]。
用标准图函数复核
Python 可选安装 python -m pip install networkx 复查。需指明 weight="weight",否则接口可按边条数理解距离。MATLAB 基础环境的 digraph 加 shortestpath 已在脚本里执行。方法 positive 用 Dijkstra,支持零权但要求非负;含负权的有向图且没有负权环时可选 mixed。 NetworkX 最短路接口 · MathWorks shortestpath
python
import networkx as nx
# 一条记录为 (起点, 终点, 分钟数),反向边须另行列出。
G = nx.DiGraph()
G.add_weighted_edges_from([
("A", "B", 4), ("A", "C", 2), ("B", "C", 1),
("B", "D", 5), ("C", "D", 8), ("C", "E", 10),
("D", "E", 2), ("D", "F", 6), ("E", "F", 2),
])
# 指定权重字段,返回的两个量分别为总分钟数和路线。
distance, route = nx.single_source_dijkstra(G, "A", target="F", weight="weight")
print(distance, route)matlab
% s、t、w 的同一位置合成一条有向边,1 到 6 对应 A 到 F。
s = [1 1 2 2 3 3 4 4 5];
t = [2 3 3 4 4 5 5 6 6];
w = [4 2 1 5 8 10 2 6 2];
G = digraph(s, t, w, 6);
% positive 选择适用于非负边权的 Dijkstra,MATLAB 先返回路线,再返回总距离。
[route, distance] = shortestpath(G, 1, 6, 'Method', 'positive');
disp(route)
disp(distance)参数练习与参考结论
将修改后的 C→D 从 6 提高到 7。由 C 进入 D 的前缀和经 B 的前缀都等于 9,两条路径并列为 13 分钟。脚本按严格小于更新前驱,通常会保留先被发现的路径。将该边提高到 8 时,经 B 的路径又成为唯一最短路。需要列出全部并列路径时,要把每个节点的前驱扩展为集合。