最短経路
正式名称
Shortest Path（ショーテストパス）
一言でいうと
目的地まで最も小さいコストで進める経路
初心者向け説明
最短経路とは、ある頂点から別の頂点まで移動するときに、重みの合計が最も小さくなる経路です。
例えば、
A --2-- B --3-- D
|
5
|
C --1-- D
なら、
A → B → D
2 + 3 = 5
と、
A → C → D
5 + 1 = 6
を比較し、コスト5のA→B→Dを選びます。
代表的な最短経路アルゴリズムとしてダイクストラ法があります。
ポイント
- ある地点から別の地点までの経路を考える
- 重みの合計が最小になる経路を探す
- ダイクストラ法などで求められる
- 最小全域木とは目的が異なる
関連用語
関連記事
- グラフ理論とは？サイクリックグラフや重み付きグラフを基礎から理解しよう
🍯 はちみつメモ
最短経路 = 目的地まで一番安く進む道