Skip to content

最短路径: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。不可达节点距离记 ∞;起点到自身距离为 0。

从零理解 ​

想象你在校园里,从宿舍 A 走到体育馆 F,想知道怎么走最省时间。先把地图抽象成一张带权网络:每个路口是一个节点,每条路是一条有向边,边权就是通行时间(或距离)。几何上「A 离 B 近不近」不重要,重要的是边权——因为 A、B 之间可能隔着一堵墙,直线很近却走不通。

Dijkstra 的思路很像「从起点一圈圈往外扩展」:先确定起点距离为 0;然后不断重复「在还没确定的点里,挑一个目前看起来最近的点,把它锁定,再看从它出发能顺路走多远」。所谓「确定」就是「这个点的最短距离已经算死了,后面不用再改」。只要所有边权都非负,「当前最近的未确定点」就必然是全局最近的点——因为它不可能再被任何「更远的点 + 一条非负权重边」抄近路追上。这就是贪心的依据,也正是负权会翻车的根源。

数学原理 ​

符号定义 ​

符号含义
G=(V,E)有向带权图,V 为节点集,E 为边集
w(u,v)边 u→v 的权值(Dijkstra 要求 w≥0)
s源点(起点)
dist[v]起点到 v 的当前最短距离上界,初始 dist[s]=0,其余 =∞
prev[v]v 的前驱节点,用于回溯路径,初始为 ∅
S已确定集合(已入集节点的 dist 为最终值)

Dijkstra:贪心 + 松弛 ​

初始化 dist[s]=0,其余 +∞;S=∅。随后重复直到 S=V 或剩余节点均不可达:

  1. 选最小:在 V∖S 中选 dist[u] 最小的节点 u,加入 S(此时 u 的最短距离确定)。
  2. 松弛:对每条出边 u→v(v∉S),若dist[u]+w(u,v)<dist[v],则更新 dist[v]=dist[u]+w(u,v) 并记 prev[v]=u。

最后从终点沿 prev 一路回溯到起点再反转,即得最短路径。贪心交换论证保证:非负权下,第 1 步选出的 u 不可能再被任何「更大的距离 + 非负边」缩短,因此可以安全确定。

为什么负权会让 Dijkstra 失效 ​

设三条边:A→B 权 2、A→C 权 3、C→B 权 −2。

  • Dijkstra 第 1 步确定 A,松弛得 dist[B]=2、dist[C]=3。
  • 第 2 步在 B(2) 与 C(3) 中选更小的 B,立即把 B 锁定为 2。
  • 但真实最短是 A→C→B=3+(−2)=1<2。Dijkstra 因负权「贪心锁定」而过早定格,给出错误答案。

结论:只要图里存在负权边,就不能用 Dijkstra(本文实现会直接抛错),应改用 Bellman-Ford(可处理负权、检测负权环)或 Floyd-Warshall。

复杂度 ​

算法场景时间复杂度空间复杂度负权
Dijkstra(O(V²) 扫描)单源,非负权O(V2)O(V+E)不支持
Dijkstra(二叉堆)单源,非负权O((V+E)log⁡V)O(V+E)不支持
Bellman-Ford单源,可负权O(VE)O(V)支持,检测负权环
Floyd-Warshall全源,可负权O(V3)O(V2)支持,检测负权环
A*单源到单点,需启发函数取决于启发式O(V+E) 起不支持(需 h 可接纳)

V 为节点数、E 为边数。本文教学实现用 O(V²) 扫描,图小、易手算;A* 在网格地图寻路中靠「到终点的距离启发」少探索节点,但要求启发函数不高估。

动态实验 ​

最短路径演示:Dijkstra(非负权)与 Bellman-Ford(负权对照)
4215810262ABCDEF

距离表(节点 → 距离,未达为 —)

A0
B4
C2
D—
E—
F—

已确定集合

A

当前选中

A

从距离表选最小未确定节点 A(距离 0),松弛出边 A→B(4)、A→C(2),更新距离表。

1 / 6
左图:节点、边权与当前最短路径链(绿色)。已确定节点填充高亮、当前选中节点描边。 每帧对应算法真实的一次迭代:Dijkstra 为「确定最小节点 + 松弛其邻边」;Bellman-Ford 为「松弛所有边一轮」。 右侧距离表随帧更新;跑完显示最短路径与距离。

参数说明:

  • 起点 / 终点:下拉选择;默认 A→F(非负权示例图)。
  • 示例:负权图:勾选后切换到 3 节点负权图 A→B=2、A→C=3、C→B=−2,演示 Bellman-Ford 并显示负权警告(此时 Dijkstra 不适用)。

动画的每一帧都对应算法真实的一次迭代:Dijkstra 模式下是「从距离表选最小未确定节点 + 松弛其出边」,与 applyStepTrace 的帧数组逐一对应,末帧距离表与一次性 dijkstra 结果完全一致(跳帧同态);负权图模式切换为 Bellman-Ford,每帧 = 一轮「松弛所有边」。下表为非负权示例图从 A 出发的完整手算过程(∞ 表示尚未到达,可逐轮核对):

轮次确定节点ABCDEF
初始—0∞∞∞∞∞
1A042∞∞∞
2C0421012∞
3B042912∞
4D04291115
5E04291113
6F04291113

最短路径 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 ==
== 全部断言通过 ==

结果图 ​

最短路径 A→F:节点、边权与最短路径高亮

关键参数 ​

参数含义本算例取值与效果
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 要求边权非负;路径成本可加
参数节点集 V、边集 E 与权值、起点(单源)/ 终点(单点到单点)
复杂度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 用 4+5=9 分钟,经 C 到 D 要 2+8=10 分钟。两条前缀都接 D→E→F,总路程分别为 13 和 14 分钟。现在 C→D 缩短到 6 分钟,经过 C 的方案变成 2+6+2+2=12 分钟,前驱关系随之改变。图中两个版本用相同的节点位置,并高亮各自的最短路,因此可以检查是哪些路段发生切换。

代码用邻接矩阵演示 Dijkstra,矩阵用 ∞ 表示无边,允许真实的通行成本为 0。另用 Bellman–Ford 复核距离表。令 dk(v) 表示至多用 k 条边到达 v 的最短距离,则

dk(v)=min(dk−1(v),minu→v(dk−1(u)+w(u,v))).

每轮只读上轮距离,恰好对应多允许一条边。若无可达负权环,可删除重复节点之间的非负代价环,故至少有一条最短路至多用 |V|−1 条边。两种算法在本图应得到相同的距离,前驱若因并列不同,仍可各自通过边权和复核。

独立运行 ​

Python 在终端安装依赖 python -m pip install numpy matplotlib,下载文件后运行 python mmf_shortest_path.py。MATLAB 将 mmf_shortest_path.m 放入当前文件夹,在命令窗口运行 result = mmf_shortest_path(),基础实验无需额外工具箱。两种脚本均输出数值并绘制图形。

下载 Python 源码 · 下载 MATLAB 源码

手写非负有向图的选点与松弛,检查从 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 的路径又成为唯一最短路。需要列出全部并列路径时,要把每个节点的前驱扩展为集合。

关联文章 ​

MathModel FAQ · 数学建模知识库