ではアルゴリズムの記述をPythonの

コードに書き換えてみます

今回はダイクストラ法を使います

ダイクストラというのは数学者の名前で

2ノード間の最短経路のアルゴリズムを考案しました

まずはネットワーク上の1個目のノードから

グラフG上の他のノードとの距離を調べます

dist_so_farはvからノードの間の距離の

未確定の値を格納する仕掛けです

以前見た手描きの図では数値が丸の中に
書かれていますが確定していません

まだ数値が入っていないノードも

ありますが確定ししだい値が入ります

最初にvからvへの距離から始めましょう

最初のノードに入る値は0です

この新たなデータ構造はfinal_distとしました

距離が確定したらここに挿入します

太字の丸に入っている値がここに入ることになります

確定したら丸を太い字で囲みます

その数値をfinal_dist に入れてdist_so_farからは削除

dist_so_farの値は空になります

全ノードを参照し終わるまで

距離の算出を繰り返します

少し不具合がありますね

グラフが切れていたら終了してしまうかもしれません

まあそれは置いておいてノードのfinal_distに

値を入れていきます

ここにすべての値が入ったか

調べるテストが必要だったかもしれません

少し修正が必要ですが連結グラフには
十分使えるので

このまま進めます

まだ分析するノードがある間は

最短の距離のノードをwとして確定します

wのfinal_distの値が確定したら

デバッグメッセージを出力します

これでfinal _distが確定しましたから
dist_so_farからは削除します

次に隣接ノードです

すべてのwの隣接ノードはｘと呼びます

隣接ノードがなければ何もしません

まだあればそのノードにdist_so_farの値を入れます

この場合の距離の値は

wまでの距離とｗからｘまでの距離を足したものです

すでに距離に値が入っている場合は

より新しい値がないか調べます

あれば置き換えます

これは緩和法などと呼ばれます

このノードについて処理しました

ｗの隣接ノードを見終わってｗについての

処理が終りました

最初のノードに近いところからまた見ていきます

すべてのノードに最終の距離の値をアサインしたら

これで終了です

ダイクストラ法をざっと確認しました 解析しましょう