[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.00,Default,,0000,0000,0000,,ではアルゴリズムの記述をPythonの
Dialogue: 0,0:00:03.00,0:00:06.00,Default,,0000,0000,0000,,コードに書き換えてみます
Dialogue: 0,0:00:06.00,0:00:09.00,Default,,0000,0000,0000,,今回はダイクストラ法を使います
Dialogue: 0,0:00:09.00,0:00:12.00,Default,,0000,0000,0000,,ダイクストラというのは数学者の名前で
Dialogue: 0,0:00:12.00,0:00:16.00,Default,,0000,0000,0000,,2ノード間の最短経路のアルゴリズムを考案しました
Dialogue: 0,0:00:16.00,0:00:19.00,Default,,0000,0000,0000,,まずはネットワーク上の1個目のノードから
Dialogue: 0,0:00:19.00,0:00:22.00,Default,,0000,0000,0000,,グラフG上の他のノードとの距離を調べます
Dialogue: 0,0:00:22.00,0:00:27.00,Default,,0000,0000,0000,,dist_so_farはvからノードの間の距離の
Dialogue: 0,0:00:27.00,0:00:32.00,Default,,0000,0000,0000,,未確定の値を格納する仕掛けです
Dialogue: 0,0:00:32.00,0:00:37.00,Default,,0000,0000,0000,,以前見た手描きの図では数値が丸の中に\N書かれていますが確定していません
Dialogue: 0,0:00:37.00,0:00:39.00,Default,,0000,0000,0000,,まだ数値が入っていないノードも
Dialogue: 0,0:00:39.00,0:00:42.00,Default,,0000,0000,0000,,ありますが確定ししだい値が入ります
Dialogue: 0,0:00:42.00,0:00:48.00,Default,,0000,0000,0000,,最初にvからvへの距離から始めましょう
Dialogue: 0,0:00:48.00,0:00:53.00,Default,,0000,0000,0000,,最初のノードに入る値は0です
Dialogue: 0,0:00:53.00,0:00:56.00,Default,,0000,0000,0000,,この新たなデータ構造はfinal_distとしました
Dialogue: 0,0:00:56.00,0:00:59.00,Default,,0000,0000,0000,,距離が確定したらここに挿入します
Dialogue: 0,0:00:59.00,0:01:03.00,Default,,0000,0000,0000,,太字の丸に入っている値がここに入ることになります
Dialogue: 0,0:01:03.00,0:01:06.00,Default,,0000,0000,0000,,確定したら丸を太い字で囲みます
Dialogue: 0,0:01:06.00,0:01:11.00,Default,,0000,0000,0000,,その数値をfinal_dist に入れてdist_so_farからは削除
Dialogue: 0,0:01:11.00,0:01:15.00,Default,,0000,0000,0000,,dist_so_farの値は空になります
Dialogue: 0,0:01:15.00,0:01:18.00,Default,,0000,0000,0000,,全ノードを参照し終わるまで
Dialogue: 0,0:01:18.00,0:01:21.00,Default,,0000,0000,0000,,距離の算出を繰り返します
Dialogue: 0,0:01:21.00,0:01:23.00,Default,,0000,0000,0000,,少し不具合がありますね
Dialogue: 0,0:01:23.00,0:01:28.00,Default,,0000,0000,0000,,グラフが切れていたら終了してしまうかもしれません
Dialogue: 0,0:01:28.00,0:01:32.00,Default,,0000,0000,0000,,まあそれは置いておいてノードのfinal_distに
Dialogue: 0,0:01:32.00,0:01:35.00,Default,,0000,0000,0000,,値を入れていきます
Dialogue: 0,0:01:35.00,0:01:38.00,Default,,0000,0000,0000,,ここにすべての値が入ったか
Dialogue: 0,0:01:38.00,0:01:41.00,Default,,0000,0000,0000,,調べるテストが必要だったかもしれません
Dialogue: 0,0:01:41.00,0:01:46.00,Default,,0000,0000,0000,,少し修正が必要ですが連結グラフには\N十分使えるので
Dialogue: 0,0:01:46.00,0:01:48.00,Default,,0000,0000,0000,,このまま進めます
Dialogue: 0,0:01:48.00,0:01:52.00,Default,,0000,0000,0000,,まだ分析するノードがある間は
Dialogue: 0,0:01:52.00,0:01:57.00,Default,,0000,0000,0000,,最短の距離のノードをwとして確定します
Dialogue: 0,0:01:57.00,0:02:01.00,Default,,0000,0000,0000,,wのfinal_distの値が確定したら
Dialogue: 0,0:02:01.00,0:02:06.00,Default,,0000,0000,0000,,デバッグメッセージを出力します
Dialogue: 0,0:02:06.00,0:02:12.00,Default,,0000,0000,0000,,これでfinal _distが確定しましたから\Ndist_so_farからは削除します
Dialogue: 0,0:02:12.00,0:02:14.00,Default,,0000,0000,0000,,次に隣接ノードです
Dialogue: 0,0:02:14.00,0:02:21.00,Default,,0000,0000,0000,,すべてのwの隣接ノードはｘと呼びます
Dialogue: 0,0:02:21.00,0:02:26.00,Default,,0000,0000,0000,,隣接ノードがなければ何もしません
Dialogue: 0,0:02:26.00,0:02:33.00,Default,,0000,0000,0000,,まだあればそのノードにdist_so_farの値を入れます
Dialogue: 0,0:02:33.00,0:02:35.00,Default,,0000,0000,0000,,この場合の距離の値は
Dialogue: 0,0:02:35.00,0:02:40.00,Default,,0000,0000,0000,,wまでの距離とｗからｘまでの距離を足したものです
Dialogue: 0,0:02:40.00,0:02:43.00,Default,,0000,0000,0000,,すでに距離に値が入っている場合は
Dialogue: 0,0:02:43.00,0:02:46.00,Default,,0000,0000,0000,,より新しい値がないか調べます
Dialogue: 0,0:02:46.00,0:02:48.00,Default,,0000,0000,0000,,あれば置き換えます
Dialogue: 0,0:02:48.00,0:02:52.00,Default,,0000,0000,0000,,これは緩和法などと呼ばれます
Dialogue: 0,0:02:52.00,0:02:54.00,Default,,0000,0000,0000,,このノードについて処理しました
Dialogue: 0,0:02:54.00,0:02:58.00,Default,,0000,0000,0000,,ｗの隣接ノードを見終わってｗについての
Dialogue: 0,0:02:58.00,0:03:00.00,Default,,0000,0000,0000,,処理が終りました
Dialogue: 0,0:03:00.00,0:03:04.00,Default,,0000,0000,0000,,最初のノードに近いところからまた見ていきます
Dialogue: 0,0:03:04.00,0:03:07.00,Default,,0000,0000,0000,,すべてのノードに最終の距離の値をアサインしたら
Dialogue: 0,0:03:07.00,0:03:09.00,Default,,0000,0000,0000,,これで終了です
Dialogue: 0,0:03:09.00,0:03:12.00,Default,,0000,0000,0000,,ダイクストラ法をざっと確認しました 解析しましょう