Japanese subtitles

← 05-15 Code for Dijkstra

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. ではアルゴリズムの記述をPythonの
  2. コードに書き換えてみます
  3. 今回はダイクストラ法を使います
  4. ダイクストラというのは数学者の名前で
  5. 2ノード間の最短経路のアルゴリズムを考案しました
  6. まずはネットワーク上の1個目のノードから
  7. グラフG上の他のノードとの距離を調べます
  8. dist_so_farはvからノードの間の距離の
  9. 未確定の値を格納する仕掛けです
  10. 以前見た手描きの図では数値が丸の中に
    書かれていますが確定していません
  11. まだ数値が入っていないノードも
  12. ありますが確定ししだい値が入ります
  13. 最初にvからvへの距離から始めましょう
  14. 最初のノードに入る値は0です
  15. この新たなデータ構造はfinal_distとしました
  16. 距離が確定したらここに挿入します
  17. 太字の丸に入っている値がここに入ることになります
  18. 確定したら丸を太い字で囲みます
  19. その数値をfinal_dist に入れてdist_so_farからは削除
  20. dist_so_farの値は空になります
  21. 全ノードを参照し終わるまで
  22. 距離の算出を繰り返します
  23. 少し不具合がありますね
  24. グラフが切れていたら終了してしまうかもしれません
  25. まあそれは置いておいてノードのfinal_distに
  26. 値を入れていきます
  27. ここにすべての値が入ったか
  28. 調べるテストが必要だったかもしれません
  29. 少し修正が必要ですが連結グラフには
    十分使えるので
  30. このまま進めます
  31. まだ分析するノードがある間は
  32. 最短の距離のノードをwとして確定します
  33. wのfinal_distの値が確定したら
  34. デバッグメッセージを出力します
  35. これでfinal _distが確定しましたから
    dist_so_farからは削除します
  36. 次に隣接ノードです
  37. すべてのwの隣接ノードはxと呼びます
  38. 隣接ノードがなければ何もしません
  39. まだあればそのノードにdist_so_farの値を入れます
  40. この場合の距離の値は
  41. wまでの距離とwからxまでの距離を足したものです
  42. すでに距離に値が入っている場合は
  43. より新しい値がないか調べます
  44. あれば置き換えます
  45. これは緩和法などと呼ばれます
  46. このノードについて処理しました
  47. wの隣接ノードを見終わってwについての
  48. 処理が終りました
  49. 最初のノードに近いところからまた見ていきます
  50. すべてのノードに最終の距離の値をアサインしたら
  51. これで終了です
  52. ダイクストラ法をざっと確認しました 解析しましょう