112数学 · 大学数学 · グラフ理論

最短経路:15辺

fx-50FH II · CMPLX · 547 bytes

最大10頂点・15辺の無向ネットワークで最小費用経路を1本求め、頂点を順番に表示した後に総費用を表示します。

  • 547 バイト
  • CMPLX モード
01

例題と解説

例題 1

大学の運用研究のオリジナル問題:美術館のロボットが番号付き展示室間を移動します。接続は双方向、費用は分単位です。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
電卓で解いてみる

例題 2

大学の運用研究のオリジナル問題:展示会のシャトル網の料金は整数単位です。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
電卓で解いてみる

例題 3

大学の運用研究のオリジナル問題:通信用の訓練網が10個の仮想端末を結びます。各双方向接続の送信費用は固定の整数です。末尾を含む全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 のみを押します。別々の2つの質問です。既知の費用0は 0EXE と入力します。

経路と費用の読み方

  • 各 Disp 画面に S からの経路頂点を1つ表示します。T を含む各頂点の後で EXE を押すと最後に総費用が出ます。−1 は経路なし。S=T では S、0 の順です。最後は AC で終了し、EXE は再実行です。

条件と制限

  • 頂点番号は整数1–10、辺費用は整数0–100、自己ループ以外の辺は最大15本です。平行辺も各1枠を使います。費用の単位を統一します。
  • 15辺版には頂点範囲・整数費用の完全な検査がありません。対応範囲内だけを入力してください。負の費用、費用の欠落、容量超過は Math ERROR。容量未満なら端点なし・非負費用の組と自己ループは無視します。満杯では2項目空欄の終了だけを受け付けます。
  • 共用680 bytesのうち547 bytesを使用し、他の領域に残るのは133 bytesです。毎回 A、B、C、D、X、Y、M、Ans を消去するため、必要な値を先に保存してください。
  • CMPLX、a+bi、Norm 1 で作成・実行します。例は Deg と P1。正常終了時は Norm 1 に戻ります。入力の i は2つの整数番号を組み合わせる記号で、虚数の費用ではありません。
  • 有向辺、負の重み、10頂点を超えるグラフは対象外です。同費用の経路は1本だけを返し、辺数最少を保証しません。有限精度の余裕が小さいため、原コードをそのまま入力します。

ログインするとプログラム全体を表示できます

利用権を確認中…

プログラムコードと付録は同時に表示されます。

利用権を確認中…

ログインするとプログラム全体を表示できます

利用権を確認中…

プログラムコードと付録は同時に表示されます。