最短経路は、決めた長さの基準が最小になる道筋です。線の本数を最小にするのか、時間や費用の合計を最小にするのかで、同じネットワークでも答えが変わります。
四つの駅を使った作例
AからDへ行く道を考えます。A–Dは直通で20分。A–Bは3分、B–Cは3分、C–Dは3分とします。すべて双方向で、待ち時間などはない説明用の模型です。
A ───── 20分 ───── D A ─3分─ B ─3分─ C ─3分─ D
| 最小にする量 | 選ぶ道 | 値 |
|---|---|---|
| 線の本数 | A→D | 1本 |
| 所要時間の合計 | A→B→C→D | 9分 |
「最短」という名前だけでは、何を最小にしたのかが足りません。乗り換えの負担を含めるなら、駅での待ち時間なども模型へ追加する必要があります。
最短距離と最短経路を分ける
距離は最小の値、経路はその値を実現する道筋です。別の道が同じ9分なら、最短距離は9分のままでも、最短経路は複数になります。一本に決める必要がある場合は、乗り換え回数などの追加基準を明示します。
地図上でまっすぐ近い駅でも、線がなければそのまま移動できません。また、線が一方通行なら帰り道も同じとは限りません。描いた位置と、到達できる関係を混ぜないようにします。
計算法にも使える条件がある
各辺を同じ1本として数えるなら、出発点から1本で届く点、2本で届く点という順に調べる幅優先探索が使えます。非負の重みを持つ場合には、ダイクストラ法が代表的な方法です。
負の重みを含む場合には、同じ方法を無条件に使えません。到達可能な負の閉路を何度でも回れて、目的地へ進めるなら、合計をいくらでも小さくできる場合もあります。現実の移動時間では普通負の値を使いませんが、計算問題では前提を確かめます。
少ないクリックなら、必ず使いやすい？
ブログで一クリックで500記事を並べる入口があっても、目的の記事が見つからなければ使いやすいとは限りません。クリック回数、探す時間、説明の分かりやすさは別の評価です。
読者の目的に合わせた一覧と関連リンクを設計した上で、どの経路が実際に使われたかを測ります。グラフ上の最短経路は、読者全員が選ぶ道の予言ではありません。つながらない点がある場合は連結成分から確認できます。