最短路径:20条边
fx-50FH II · CMPLX · 637 bytes
在最多十个节点、20条边的无向网络中求一条最低成本路径,依次显示节点,最后显示总成本。
- 637 字节
- CMPLX 模式
例题详解
例题一
大学运筹学原创练习:博物馆机器人要在编号展厅之间移动。列出的连接均可双向使用,成本单位是分钟。求由节点 2 到 6 的最短时间路径及总时间。
列出的边均为无向边;未列出的连接不存在。边表(a–b:成本):2–1: 7; 2–3: 4; 1–4: 5; 3–4: 2; 3–5: 8; 4–6: 3; 5–6: 2; 1–5: 12
答案
标准解法(不用计算器)
- 从 S 执行 Dijkstra。下列 u 是本轮确定的节点,d(v) 是更新后的暂定距离;∞ 表示暂时不可达。
- u=2, d(2)=0; d(1)=7, d(3)=4
- u=3, d(3)=4; d(4)=6, d(5)=12
- u=4, d(4)=6; d(6)=9
- u=1, d(1)=7; ∅
- u=6, d(6)=9; d(5)=11
- 沿前驱回溯,并直接加总路径的边成本:2 → 3 → 4 → 6; 总成本 4+2+3=9 min
例题二
大学运筹学原创练习:展览接驳网络以整数票价单位计费。7–8 的连接免费,成本确实是 0。求由节点 7 到 2 的最低票价路径及总票价。
列出的边均为无向边;未列出的连接不存在。边表(a–b:成本):7–8: 0; 8–9: 3; 9–2: 4; 7–1: 9; 1–2: 2; 8–2: 10; 9–1: 1
答案
标准解法(不用计算器)
- 从 S 执行 Dijkstra。下列 u 是本轮确定的节点,d(v) 是更新后的暂定距离;∞ 表示暂时不可达。
- u=7, d(7)=0; d(1)=9, d(8)=0
- u=8, d(8)=0; d(2)=10, d(9)=3
- u=9, d(9)=3; d(1)=4, d(2)=7
- u=1, d(1)=4; d(2)=6
- u=2, d(2)=6; ∅
- 沿前驱回溯,并直接加总路径的边成本:7 → 8 → 9 → 1 → 2; 总成本 0+3+1+2=6
例题三
大学运筹学原创练习:通信训练网络连接十个虚拟终端。每条双向连接有固定的整数传送成本。依清单顺序输入全部 20 条连接,求由 1 到 10 的最低成本路径及总成本,必须包括最后的连接。
列出的边均为无向边;未列出的连接不存在。边表(a–b:成本):1–2: 5; 2–3: 7; 3–4: 4; 4–5: 6; 5–6: 3; 6–7: 8; 7–8: 2; 8–9: 5; 9–10: 4; 1–6: 9; 2–7: 9; 3–8: 9; 4–9: 9; 5–10: 9; 2–9: 1; 1–4: 1; 4–7: 1; 7–10: 1; 1–8: 9; 3–10: 8
答案
标准解法(不用计算器)
- 从 S 执行 Dijkstra。下列 u 是本轮确定的节点,d(v) 是更新后的暂定距离;∞ 表示暂时不可达。
- u=1, d(1)=0; d(2)=5, d(4)=1, d(6)=9, d(8)=9
- u=4, d(4)=1; d(3)=5, d(5)=7, d(7)=2, d(9)=10
- u=7, d(7)=2; d(8)=4, d(10)=3
- u=10, d(10)=3; d(9)=7
- 沿前驱回溯,并直接加总路径的边成本:1 → 4 → 7 → 10; 总成本 1+1+1=3
适用场景
大学数学 · 运筹学。处理固定网络及非负、可相加的成本。这是图论算法练习,不会自行判断道路方向或行程条件。
输入网络
- 第一个 Y? 输入 S+Ti,S 是起点,T 是终点。之后交替在 Y? 输入无向边 a+bi,在 M? 输入该边成本。i 用 ENG;不用输入节点数或边数。
- 完成后,下一个 Y? 直接按 EXE,再在 M? 直接按 EXE;是两个不同提示。已知零成本必须按 0EXE。
读取路径及成本
- 每个 Disp 画面是一个路径节点,由 S 开始。每个节点(包括 T)之后按 EXE,才看到最后总成本。−1 表示无路径;S=T 时显示 S,再显示 0。最后按 AC 离开;EXE 会重新执行。
条件及限制
- 节点编号限整数 1–10,边成本限整数 0–100,最多储存 20 条非自环边。平行边各占一槽;所有成本使用相同单位。
- 20边版会检查端点及成本的整数和范围。只漏一栏、不合法值或超容量会出 Math ERROR。未满容量时合法自环会忽略;满容量后只接受两栏留空结束。
- 程序占共用 680 bytes 中的 637 bytes,其他槽合计余 43 bytes。每次执行清除 A、B、C、D、X、Y、M 及 Ans;先备份原值。
- 建立及执行均用 CMPLX、a+bi、Norm 1;例题采用 Deg 和 P1。正常结束恢复 Norm 1;输入的 i 只编码两个整数节点,不是虚数成本。
- 不支持有向边、负权重或超过十个节点。等成本路径可能不止一条,只返回其中一条,不保证边数最少。完整原码必须照输;紧密编码的有限精度余量很小。
正在确认使用权限…