112數學 · 大學數學 · 圖論

最短路徑:15條邊

fx-50FH II · CMPLX · 547 bytes

在最多十個節點、15條邊的無向網絡中求一條最低成本路徑,依次顯示節點,最後顯示總成本。

  • 547 bytes
  • 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
用計算機做這題

例題三

大學運籌學原創練習:通訊訓練網絡連接十個虛擬終端。每條雙向連接有固定的整數傳送成本。依清單順序輸入全部 15 條連接,求由 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 → 2 → 9 → 10; 總成本 5+1+4=10
標準解法(不用計算機)
  1. 從 S 執行 Dijkstra。下列 u 是本輪確定的節點,d(v) 是更新後的暫定距離;∞ 表示暫時不可達。
  2. u=1, d(1)=0; d(2)=5, d(6)=9
  3. u=2, d(2)=5; d(3)=12, d(7)=14, d(9)=6
  4. u=9, d(9)=6; d(4)=15, d(8)=11, d(10)=10
  5. u=6, d(6)=9; d(5)=12
  6. u=10, d(10)=10; ∅
  7. 沿前驅回溯,並直接加總路徑的邊成本:1 → 2 → 9 → 10; 總成本 5+1+4=10
用計算機做這題
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,最多儲存 15 條非自環邊。平行邊各佔一槽;所有成本使用相同單位。
  • 15邊版沒有完整的節點範圍及整數成本驗證器,只能輸入支援範圍內的資料。負成本、漏成本或超容量會出 Math ERROR。未滿容量時,漏端點但填非負成本,或輸入自環,該筆會忽略;滿容量後只接受兩欄留空結束。
  • 程式佔共用 680 bytes 中的 547 bytes,其他槽合計餘 133 bytes。每次執行清除 A、B、C、D、X、Y、M 及 Ans;先備份原值。
  • 建立及執行均用 CMPLX、a+bi、Norm 1;例題採 Deg 和 P1。正常結束恢復 Norm 1;輸入的 i 只編碼兩個整數節點,不是虛數成本。
  • 不支援有向邊、負權重或超過十個節點。等成本路徑可能不止一條,只回傳其中一條,不保證邊數最少。完整原碼必須照輸;緊密編碼的有限精度餘量很小。

登入即可解鎖完整程式

正在確認使用權限…

程式碼和附錄會一併解鎖。

正在確認使用權限…

登入即可解鎖完整程式

正在確認使用權限…

程式碼和附錄會一併解鎖。