最短経路:15辺
fx-50FH II · CMPLX · 547 bytes
最大10頂点・15辺の無向ネットワークで最小費用経路を1本求め、頂点を順番に表示した後に総費用を表示します。
- 547 バイト
- CMPLX モード
例題と解説
例題 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
答え
標準的な解き方(電卓なし)
- 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
例題 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
答え
標準的な解き方(電卓なし)
- 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
例題 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
答え
標準的な解き方(電卓なし)
- S から Dijkstra を適用します。u は新たに確定した頂点、d(v) は更新後の暫定距離、∞ はまだ到達不能を表します。
- u=1, d(1)=0; d(2)=5, d(6)=9
- u=2, d(2)=5; d(3)=12, d(7)=14, d(9)=6
- u=9, d(9)=6; d(4)=15, d(8)=11, d(10)=10
- u=6, d(6)=9; d(5)=12
- u=10, d(10)=10; ∅
- 前駆をたどり、経路上の費用を直接加算します:1 → 2 → 9 → 10; 総費用 5+1+4=10
使いどころ
大学数学・オペレーションズリサーチ。固定されたネットワークの非負で加算可能な費用を扱います。道路の方向や移動条件を自動判断する機能ではありません。
ネットワークの入力
- 最初の 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本だけを返し、辺数最少を保証しません。有限精度の余裕が小さいため、原コードをそのまま入力します。
利用権を確認中…