ダイクストラの最短経路アルゴリズム-詳細で視覚的な紹介

ようこそ!ダイクストラのアルゴリズムを常に学び、理解したいのであれば、この記事はあなたにぴったりです。ステップバイステップのグラフィカルな説明で、それが舞台裏でどのように機能するかを見ることができます。

あなたは学びます:

  • 基本的なグラフの概念(簡単なレビュー)。
  • ダイクストラのアルゴリズムが使用される目的。
  • ステップバイステップの例を使用して、舞台裏でどのように機能するか。

さぁ、始めよう。✨

🔹グラフの紹介

グラフの簡単な紹介から始めましょう。

基本概念

グラフは、要素のペア間の「接続」を表すために使用されるデータ構造です。

  • これらの要素はノードと呼ばれます。それらは、実際のオブジェクト、人、またはエンティティを表します。
  • ノード間の接続はエッジと呼ばれます

これはグラフのグラフィック表現です。

ノードは色付きの円で表され、エッジはこれらの円を結ぶ線で表されます。

💡ヒント: 2つのノードの間にエッジがある場合、それらは接続されます。

アプリケーション

グラフは、実際のシナリオに直接適用できます。たとえば、グラフを使用して、ノードが製品を送受信する施設を表し、エッジがそれらを接続する道路またはパスを表す輸送ネットワークをモデル化できます(以下を参照)。

グラフの種類

グラフは次のようになります。

  • 無向:接続されたノードのすべてのペアについて、一方のノードからもう一方のノードに両方向に移動できる場合。
  • 指示接続されたノードのすべてのペアについて、特定の方向に1つのノードから別のノードにのみ移動できる場合。有向エッジを表すために、単純な線の代わりに矢印を使用します。

💡ヒント:この記事では、無向グラフを使用します。

加重グラフ

体重グラフは、その縁「重み」又は「コスト」を有するグラフです。エッジの重みは、距離、時間、または接続するノードのペア間の「接続」をモデル化するものを表すことができます。

たとえば、以下の加重グラフでは、各エッジの横に青い数字が表示されます。この数値は、対応するエッジの重みを表すために使用されます。

💡ヒント:これらの重みは、ダイクストラのアルゴリズムに不可欠です。理由はすぐにわかります。

🔸ダイクストラのアルゴリズムの紹介

グラフの基本的な概念がわかったところで、この驚くべきアルゴリズムに飛び込みましょう。

  • 目的とユースケース
  • 歴史
  • アルゴリズムの基本
  • 要件

目的とユースケース

ダイクストラのアルゴリズムを使用すると、グラフ内のノード間の最短経路を見つけることができます。特に、ノード(「ソースノード」と呼ばれる)からグラフ内の他のすべてのノードへの最短経路を見つけることができ、最短経路ツリーが生成されます。

このアルゴリズムは、現在の場所と目的地の間の最短経路を見つけるためにGPSデバイスで使用されます。業界、特にモデリングネットワークを必要とするドメインで幅広いアプリケーションがあります。

歴史

このアルゴリズムは、優秀なオランダのコンピューター科学者でありソフトウェアエンジニアであるDr. Edsger W.Dijkstraによって作成および公開されました。

1959年に、彼は「グラフに関連する2つの問題に関するメモ」というタイトルの3ページの記事を公開し、新しいアルゴリズムについて説明しました。

2001年のインタビューで、ダイクストラ博士はアルゴリズムを設計した方法と理由を明らかにしました。

ロッテルダムからフローニンゲンへの最短の移動方法は何ですか?約20分で設計した最短経路のアルゴリズムです。ある朝、若い婚約者と一緒にアムステルダムで買い物をしていて、疲れていたので、カフェテラスに座ってコーヒーを飲みました。これができるかどうかを考えていたところ、最短経路のアルゴリズムを設計しました。 。私が言ったように、それは20分の発明でした。実際、3年後の1959年に出版されました。出版物はまだかなりいいです。とても素敵な理由の一つは、鉛筆と紙を使わずにデザインしたことです。鉛筆と紙がなければ、避けられない複雑さをすべて回避せざるを得なくなります。最終的に、そのアルゴリズムは、私の大きな驚きに、私の名声の基礎の1つになりました。 —記事EdsgerWで引用されているように。Edsger W.DijkstraへのインタビューからのDijkstra。

信じられないでしょう?わずか20分で、Dijkstra博士は、コンピュータサイエンスの歴史の中で最も有名なアルゴリズムの1つを設計しました。

ダイクストラのアルゴリズムの基礎

  • ダイクストラのアルゴリズムは基本的に、選択したノード(ソースノード)から始まり、グラフを分析して、そのノードとグラフ内の他のすべてのノードとの間の最短パスを見つけます。
  • アルゴリズムは、各ノードからソースノードまでの現在知られている最短距離を追跡し、より短いパスが見つかるとこれらの値を更新します。
  • アルゴリズムが送信元ノードと別のノード間の最短パスを検出すると、そのノードは「訪問済み」としてマークされ、パスに追加されます。
  • このプロセスは、グラフ内のすべてのノードがパスに追加されるまで続きます。このようにして、各ノードに到達するために可能な最短パスに従って、ソースノードを他のすべてのノードに接続するパスがあります。

要件

ダイクストラのアルゴリズムは、正の重みを持つグラフでのみ機能します。これは、プロセス中に、最短パスを見つけるためにエッジの重みを追加する必要があるためです。

グラフに負の重みがある場合、アルゴリズムは正しく機能しません。ノードが「訪問済み」としてマークされると、そのノードへの現在のパスが、そのノードに到達するための最短パスとしてマークされます。また、このステップが発生した後に総重量を減らすことができる場合、負の重みによってこれが変わる可能性があります。

🔹ダイクストラのアルゴリズムの例

このアルゴリズムについて詳しく理解できたので、ステップバイステップの例を使用して、舞台裏でどのように機能するかを見てみましょう。

このグラフがあります:

アルゴリズムは、ノード0からグラフ内の他のすべてのノードへの最短パスを生成します。

💡ヒント:このグラフでは、エッジの重みが2つのノード間の距離を表すと想定します。

グラフ内のすべてのノードについて、ノードからノードへ、ノードからノードへ、ノードからノード0へなどの最短パスがあります。10203

最初に、この距離のリストがあります(以下のリストを参照してください)。

  • ソースノードからそれ自体までの距離は0です。この例では、ソースノードはノードになります0が、選択した任意のノードにすることができます。
  • ソースノードから他のすべてのノードまでの距離はまだ決定されていないため、最初は無限大記号を使用してこれを表します。

まだアクセスされていないノード(パスに含まれていないノード)を追跡するために、このリスト(以下を参照)もあります。

💡ヒント:すべてのノードがパスに追加されると、アルゴリズムが完了することを忘れないでください。

ノードから開始することを選択しているので0、このノードを訪問済みとしてマークできます。同様に、未訪問のノードのリストからそれを削除し、図の対応するノードに赤い境界線を追加します。

次に、ノード0から隣接ノードまでの距離のチェックを開始する必要があります。ご覧のとおり、これらはノードで1あり2(赤いエッジを参照):

💡ヒント:これは、2つの隣接するノードを最短パスにすぐに追加するという意味ではありません。このパスにノードを追加する前に、ノードに到達するための最短パスが見つかったかどうかを確認する必要があります。利用可能なオプションを確認するために、最初の調査プロセスを行っているだけです。

ノード0からノード1およびノードまでの距離2を、それらをノード0(ソースノード)に接続するエッジの重みで更新する必要があります。これらの重みはそれぞれ2と6です。

隣接するノードの距離を更新した後、次のことを行う必要があります。

  • 現在の既知の距離に基づいて、ソースノードに最も近いノードを選択します。
  • 訪問済みとしてマークします。
  • パスに追加します。

距離のリストを確認する1と、ノードのソースノードまでの距離が最短(距離2)であることがわかるので、それをパスに追加します。

この図では、これを赤いエッジで表すことができます。

リスト内で赤い四角でマークして、「アクセス済み」であり、このノードへの最短パスが見つかったことを示します。

未訪問のノードのリストから削除します。

次に、新しい隣接ノードを分析して、それらに到達するための最短パスを見つける必要があります。すでに最短パス(赤いエッジでマークされたパス)の一部であるノードに隣接するノードのみを分析します。

ノード3およびノードが2両方それらがノードに直接接続されているため、パスに既にあるノードに隣接する0ノード1あなたは以下を参照することができるように、それぞれ、。これらは、次のステップで分析するノードです。

ソースノードからノードまでの距離はすでに2リストに記載されているので、今回は距離を更新する必要はありません。ソースノードから新しい隣接ノード(ノード3)までの距離を更新するだけで済みます。

この距離は7です。理由を見てみましょう。

ソースノードから別のノード(この場合はノード3)までの距離を見つけるために、そのノードに到達するための最短パスを形成するすべてのエッジの重みを追加します。

  • ノードの場合3パスを形成するエッジの重みを追加するため、合計距離は7になります0 -> 1 -> 3(エッジの場合は2、エッジの0 -> 1場合は5 1 -> 3)。

隣接するノードまでの距離がわかったので、パスに追加するノードを選択する必要があります。ソースノードまでの距離が最も短い(現在知られている)未訪問ノードを選択する必要があります。

距離のリストから、これが2距離6のノードであることがすぐにわかります。

ノードの周りに赤い境界線と赤いエッジを付けて、グラフィカルにパスに追加します。

また、距離のリストに小さな赤い四角を追加し、未訪問のノードのリストから削除することで、訪問済みとしてマークします。

ここで、プロセスを繰り返して、ソースノードから新しい隣接ノード(ノード)への最短パスを見つける必要があります3

2つの可能なパス0 -> 1 -> 3またはが存在することがわかります0 -> 2 -> 3。どれが最短経路であるかをどのように決定できるか見てみましょう。

ノードに3は、以前に記録されたリストにすでに距離があります(7、以下のリストを参照)。この距離は、パスをたどるために交差する必要がある2つのエッジの重み5と2を追加した前の手順の結果です0 -> 1 -> 3

しかし今、私たちは別の選択肢があります。私たちは道を歩むことを選択した場合0 -> 2 -> 3、我々は2つのエッジを辿る必要があるだろう0 -> 22 -> 3重みで68それぞれ、これは合計距離14を表します。

明らかに、最初の(既存の)距離は短い(7対14)ので、元のパスを維持することを選択します0 -> 1 -> 3新しいパスが短い場合にのみ距離を更新します。

したがって、最初の選択肢を使用して、このノードをパスに追加します0 -> 1 -> 3

このノードを訪問済みとしてマークし、未訪問ノードのリストから削除します。

ここで、このプロセスをもう一度繰り返します。

これまでアクセスしたことのない新しい隣接ノードを確認する必要があります。今回は、これらのノードはノードに隣接しているため、ノード45ノード3です。

これらのノードからソースノードまでの距離を更新し、可能であれば常に短いパスを見つけようとします。

  • ノードの場合4パスからの  距離は170 -> 1 -> 3 -> 4です。
  • ノードの場合5パスからの距離は220 -> 1 -> 3 -> 5です。

💡ヒント:最短パス(赤でマーク)の延長のみを検討できることに注意してください。最短パスに追加されていないエッジを通過するパスを考慮することはできません(たとえば、エッジを通過するパスを形成することはできません2 -> 3)。

どの未訪問ノードを今訪問済みとしてマークするかを選択する必要があります。この場合、4距離のリストで最短の距離を持っているため、ノードです。ダイアグラムにグラフィカルに追加します。

また、リストに小さな赤い四角を追加して、「訪問済み」としてマークします。

そして、未訪問のノードのリストからそれを削除します。

そして、このプロセスをもう一度繰り返します。隣接するノードをチェックします:ノード5とノード6。すでに訪問済みとしてマークされ、パスに追加されているノードからそれらに到達するためにたどることができる各可能なパスを分析する必要があります。

ノードの場合5

  • 最初のオプションは、ソースノードから22の0 -> 1 -> 3 -> 5距離(2 + 5 + 15)を持つパスをたどることです。この距離は、前のステップの距離のリストにすでに記録されています。
  • 2番目のオプションは、ソースノードから23の0 -> 1 -> 3 -> 4 -> 5距離(2 + 5 + 10 + 6)を持つパスをたどることです。

明らかに、最初のパスは短いので、ノードに選択します5

ノードの場合6

  • 使用可能なパスはです0 -> 1 -> 3 -> 4 -> 6。これは、ソースノードから19の距離(2 + 5 + 10 + 2)です。

最短(現在既知)の距離でノードを訪問済みとしてマークします。この場合、ノード6

そして、未訪問のノードのリストからそれを削除します。

これで、このパス(赤でマーク)ができました:

まだアクセスされていないノードは、ノードの1つだけ5です。パスにそれを含める方法を見てみましょう。

パスに5追加されたノードからノードに到達するために取ることができる3つの異なるパスがあります。

  • オプション1:0 -> 1 -> 3 -> 5距離22(2 + 5 + 15)。
  • オプション2:0 -> 1 -> 3 -> 4 -> 5距離23(2 + 5 + 10 + 6)。
  • オプション3:0 -> 1 -> 3 -> 4 -> 6 -> 5距離25(2 + 5 + 10 + 2 + 6)。

最短経路を選択します:0 -> 1 -> 3 -> 5距離22

ノードを訪問済みとしてマークし、未訪問ノードのリストから削除します。

そして、ボイラ!0グラフ内のノードから各ノードへの最短パスで最終結果が得られます。

この図では、赤い線は最短パスに属するエッジを示しています。ノードから始まるグラフ内の特定のノードに到達するための最短パスをたどるには、これらのエッジをたどる必要があります0

たとえば、ノード6から開始してノードに到達する場合0は、赤いエッジをたどるだけで、最短パスを0 -> 1 -> 3 -> 4 - > 6自動的にたどります。

🔸まとめ

  • グラフは、オブジェクト、人、またはエンティティ間の接続をモデル化するために使用されます。それらには、ノードとエッジという2つの主要な要素があります。ノードはオブジェクトを表し、エッジはこれらのオブジェクト間の接続を表します。
  • ダイクストラのアルゴリズムは、特定のノード(「ソースノード」と呼ばれます)とグラフ内の他のすべてのノードの間の最短パスを見つけます。
  • このアルゴリズムは、エッジの重みを使用して、ソースノードと他のすべてのノード間の合計距離(重み)を最小化するパスを見つけます。

あなたが私の記事を気に入ってくれて、それがお役に立てば幸いです。これで、ダイクストラのアルゴリズムが舞台裏でどのように機能するかがわかりました。Twitter @EstefaniaCassNで私をフォローし、私のオンラインコースをチェックしてください。