113数学 · 大学数学 · 图论

最短路径:20条边

fx-50FH II · CMPLX · 637 bytes

在最多十个节点、20条边的无向网络中求一条最低成本路径,依次显示节点,最后显示总成本。

  • 637 字节
  • CMPLX 模式
01

例题详解

例题一

大学运筹学原创练习:博物馆机器人要在编号展厅之间移动。列出的连接均可双向使用,成本单位是分钟。求由节点 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

答案
2 → 3 → 4 → 6; 总成本 4+2+3=9 min
标准解法(不用计算器)
  1. 从 S 执行 Dijkstra。下列 u 是本轮确定的节点,d(v) 是更新后的暂定距离;∞ 表示暂时不可达。
  2. u=2, d(2)=0; d(1)=7, d(3)=4
  3. u=3, d(3)=4; d(4)=6, d(5)=12
  4. u=4, d(4)=6; d(6)=9
  5. u=1, d(1)=7; ∅
  6. u=6, d(6)=9; d(5)=11
  7. 沿前驱回溯,并直接加总路径的边成本: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

答案
7 → 8 → 9 → 1 → 2; 总成本 0+3+1+2=6
标准解法(不用计算器)
  1. 从 S 执行 Dijkstra。下列 u 是本轮确定的节点,d(v) 是更新后的暂定距离;∞ 表示暂时不可达。
  2. u=7, d(7)=0; d(1)=9, d(8)=0
  3. u=8, d(8)=0; d(2)=10, d(9)=3
  4. u=9, d(9)=3; d(1)=4, d(2)=7
  5. u=1, d(1)=4; d(2)=6
  6. u=2, d(2)=6; ∅
  7. 沿前驱回溯,并直接加总路径的边成本: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

答案
1 → 4 → 7 → 10; 总成本 1+1+1=3
标准解法(不用计算器)
  1. 从 S 执行 Dijkstra。下列 u 是本轮确定的节点,d(v) 是更新后的暂定距离;∞ 表示暂时不可达。
  2. u=1, d(1)=0; d(2)=5, d(4)=1, d(6)=9, d(8)=9
  3. u=4, d(4)=1; d(3)=5, d(5)=7, d(7)=2, d(9)=10
  4. u=7, d(7)=2; d(8)=4, d(10)=3
  5. u=10, d(10)=3; d(9)=7
  6. 沿前驱回溯,并直接加总路径的边成本:1 → 4 → 7 → 10; 总成本 1+1+1=3
用计算器做这题
02

适用场景

大学数学 · 运筹学。处理固定网络及非负、可相加的成本。这是图论算法练习,不会自行判断道路方向或行程条件。

输入网络

  • 第一个 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 只编码两个整数节点,不是虚数成本。
  • 不支持有向边、负权重或超过十个节点。等成本路径可能不止一条,只返回其中一条,不保证边数最少。完整原码必须照输;紧密编码的有限精度余量很小。

登录即可解锁完整程序

正在确认使用权限…

程序代码和附录会一并解锁。

正在确认使用权限…

登录即可解锁完整程序

正在确认使用权限…

程序代码和附录会一并解锁。