導入
グラフ理論では、最短経路問題を解くためにダイクストラのアルゴリズムが使用されます。たとえば、地域の道路網を把握して、ある都市から別の都市に移動する最短経路を決定することができます。これは、エッジにリンクされた重みが正またはゼロである接続グラフに適用されます。
このアルゴリズムは、発明者であるオランダのコンピューター科学者エドガー・ダイクストラにちなんで名付けられ、1959 年に公開されました。
複雑性理論では、このアルゴリズムが多項式であることを証明します。
例に関する原則
これには、初期データから、開始頂点からの最小距離の増加順にさまざまな頂点が分類されるサブグラフを徐々に構築することが含まれます。この距離は、取得されたエッジの重みの合計に対応します。
最初のステップは、開始頂点を脇に置き、グラフ内の開始頂点から他の頂点までの距離を特定することです。頂点を開始頂点に接続する円弧がない場合、この距離は無限であり、この頂点を開始頂点に接続する円弧が存在する場合はnであり、最小の重み (複数の円弧がある場合) はnです。
2 番目のステップでは、開始頂点までの距離が最短となる頂点を見つけて脇に置きます。残りのすべての頂点について、以前に見つけた距離と、今確保した頂点を介して取得した距離を比較し、最小値のみを保持します。そして、頂点がなくなるまで、または到着頂点が選択されるまで、この方法を続けます。
都市Aと都市Jの間の距離
次の例は、グラフ内の最短パスを解決する一連の手順を示しています。ノードは文字で識別される都市を象徴し、エッジはこれらの都市間の距離を示します。私たちは都市 A から都市 J に行く最短ルートを決定しようとしています。
 ステップ 1: 都市 A からは、B、C、E の 3 つの都市にアクセスできるため、それぞれの重み 85、217、173 が割り当てられ、他の都市には無限の距離が割り当てられます。 |  ステップ 2: 最短距離は都市 B につながる距離です。都市 B を通過すると都市 F への道が開きます (85+80 = 165)。 |
 ステップ 3: 次に短い距離は町 F です。町 F を通過すると、町 I (415) への道が開きます。 |  ステップ 4: 次に短い距離は町 E です。町 E を通過すると、町 J (675) へのルートが開きます。 |
 ステップ 5: 次に短い距離は町 C につながります。町 C を通過すると、町 G (403) と町 H (320) へのルートが開きます。 |  ステップ 6: 次に短い距離は都市 H(320) につながります。町 H を通過すると、町 D へのルートと町 J (487<675) へのショートカットが開きます。 |
 ステップ 7: 次に短い距離は都市 G につながり、他の距離は変わりません。 |  ステップ 8: 次に短い距離は町 I につながります。町 I を通過すると、興味のない町 J への道が開きます (415+ 84 > 487)。 |
 ステップ 9: 次に短い距離は J 町 (487) につながります。 |
したがって、A から J に至る最短経路がわかります。その経路は C と H を通過し、長さは 487 km です。
現在、ダイクストラのアルゴリズムは、GPS などのいくつかのコンピューター アプリケーションで使用されています。さらに、たとえばGoogle は、このアルゴリズムを導入して、 Google マップやGoogle Earthのいくつかの機能を改善することができました。
テーブルプレゼンテーション
一連のグラフによる説明は少し長くなる場合があります。また、図面の端で最短パスを特定することも少し難しくなります。したがって、ダイスクトラのアルゴリズムは、各ステップが行に対応するテーブルを使用して実行されることがよくあります。
さまざまな都市を接続する有向円弧のマトリックスから:
| Aへ | Bへ | Cへ | Dへ | Eへ | Fへ | Gへ | Hへ | 私に | Jへ | |
|---|---|---|---|---|---|---|---|---|---|---|
| Aから | 0 | 85 | 217 | ∞ | 173 | ∞ | ∞ | ∞ | ∞ | ∞ |
| Bから | 85 | 0 | ∞ | ∞ | ∞ | 80 | ∞ | ∞ | ∞ | ∞ |
| 12月 | 217 | ∞ | 0 | ∞ | ∞ | ∞ | 186 | 103 | ∞ | ∞ |
| Dから | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | ∞ | 183 | ∞ | ∞ |
| Eから | 173 | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | ∞ | ∞ | 502 |
| Fさんより | ∞ | 80 | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 250 | ∞ |
| Gから | ∞ | ∞ | 186 | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | ∞ |
| Hさんより | ∞ | ∞ | 103 | 183 | ∞ | ∞ | ∞ | 0 | ∞ | 167 |
| 私から | ∞ | ∞ | ∞ | ∞ | ∞ | 250 | ∞ | ∞ | 0 | 84 |
| Jから | ∞ | ∞ | ∞ | ∞ | 502 | ∞ | ∞ | 167 | 84 | 0 |
頂点から開始頂点までの距離が同じ列にグループ化されたテーブルを作成します。選択した頂点には下線が付きます。新しい頂点の選択によって開かれたルートの距離は、既に計算された距離よりも大きい場合は取り消し線で表示されます。頂点が選択されると、その頂点までの最小距離が判明したため、この頂点から開始点までの他の距離を探すことは役に立ちません。
| Bへ | Cへ | Dへ | Eへ | Fへ | Gへ | Hへ | 私に | Jへ | |
|---|---|---|---|---|---|---|---|---|---|
| もっている | 85 | 217 | ∞ | 173 | ∞ | ∞ | ∞ | ∞ | ∞ |
| B( 85A ) | – | 217 | ∞ | 173 | 165 | ∞ | ∞ | ∞ | ∞ |
| F( 165B ) | – | 217 | ∞ | 173 | – | ∞ | ∞ | 415 | ∞ |
| E( 173A ) | – | 217 | ∞ | – | – | ∞ | ∞ | 415 | 675 |
| C( 217A ) | – | – | ∞ | – | – | 403 | 320 | 415 | 675 |
| H(320 ℃ ) | – | – | 503 | – | – | 403 | – | 415 | 487 |
| G(403 ℃ ) | – | – | 503 | – | – | – | – | 415 | 487 |
| I(415 °F ) | – | – | 503 | – | – | – | – | – | |
| J( 487H ) | – | – | 503 | – | – | – | – | – | – |
| D( 503H ) | – | – | – | – | – | – | – | – | – |
このテーブルを作成すると、都市 A から都市 J までの最短距離だけでなく、たどる経路 (J – H – C – A)、およびクロワッサンの順序で配置された都市 A から他の都市までのすべての最短距離もわかります。 。