[FGISC。Nanro] 未來開端

使用演算法：圖形演算法－最短路徑之Dijkstra

看了很久才看懂題目
感謝sa同學的指導\(￣▽￣\)﹏﹏

雖然提示給BFS
不過為了練習Dijkstra
所以我是用Dijkstra做的  //一開始有點用到BFS的方法了囧" BFS寫太多一一"

換成路徑來看 這題 等於是要求
唐喬望尼 跟每個人之間的最短距離
//Don Giovanni就是唐喬望尼  莫札特的歌劇  Don Giovanni是色胚= =+

Dijkstra的原理是
搜尋一次 找距離原點最小距離的那個點
這時候便可以確定，沒有任何從原點經過其他的點到那個點的距離
比原點直接距離他的距離還要小

然後　我們再看看
藉由這個點
可以到達哪些　本來到不了的點
或者是使原點到該點的距離更小
//然後就可以更新表格

然後我們再看 哪一點我們還沒有處理過 然後原點到他的距離最短
再通過那個點做相同處理
一直到每個點都被處理過一次 //或者是走到他有規定的終點

就可以知道原點跟每個點的最短距離是多少了

         1
0.──1.        2 4.
 ╲      │     ╱ ｜
      ╲ │╱      ｜         看的出來嗎 有點點的是編號 沒點點的是跟原點的距離
     1   2.───3.2

依序來看是這樣

         1
0.──1.           4.
 ╲      │     ╱ ｜
      ╲ │╱      ｜
      1   2.───3.


           1
0.──1.           4.
 ╲      │     ╱ ｜
      ╲ │╱      ｜
      1   2.───3.

         1　　　2
0.──1.           4.
 ╲      │     ╱ ｜
      ╲ │╱      ｜
      1   2.───3.2

         1      　  2
0.──1.           4.
 ╲      │     ╱ ｜
      ╲ │╱      ｜
      1   2.───3.2


         1            2
0.──1.           4.
 ╲      │     ╱ ｜
      ╲ │╱      ｜
      1   2.───3.2

大概是這個樣子了。

照這樣的過程去做 應該沒什麼問題了～