YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 05-13 Simulate this Algorithm

Get Embed Code
3 Languages

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

  1. 注意深く考えないとEに行くまでの
  2. 最短の回数を選んでしまうかもしれません
  3. この場合だとAから2つパスが考えられますが
  4. Dまで2回の移動で11に7を加算して
  5. 18と答えてしまった人はいませんか
    正しくは最初にDまでの最小の距離を考えます
  6. このパスを行けば最小の値は10です
  7. 4+1+5=10なので7を加算して17になります
  8. シミュレートしてみましょう
  9. まずAからCとBに展開します
  10. 最短のCをマークして確定します
  11. 次はCからエッジを展開します
  12. CからはDまたはBにエッジが引けます
  13. CからBのパスは1の重さがあり4を加算すると
  14. この値を5にして新しいノードDを追加します
  15. CからDは7なので4+7で11になってしまいます
  16. つまりまだ到達していないノードBとDでは
  17. Bまでのトータル5が最も小さい値になります
  18. ここもマークして今度はBからは
  19. Dに至る1本のパスしかありません 値は5です
  20. 5を加算するとDまでの値が11から10に向上しました
  21. 他にBから展開できるノードはありません
  22. これもマークして今度はFとEに展開します
  23. Fへは20でEまでは17です
  24. Eからの距離を特定するまでは
  25. Fを確定できません
  26. より短いパスの値は19です
  27. 理解できたところでコードにしてみましょう