小弟學店資工系 簡單介紹一下這個演算法
作者在文中已經有提到是dijkstra's algorithm 戴克斯奧拉演算法
主要用在最短路徑的探討上
其實可以應用在很複雜的鐵路系統
可惜台灣高鐵連一圈都沒有連起來 所以簡單很多
範例影片 https://www.youtube.com/watch?v=5GT5hYzjNoo&t=5s
我們拿高鐵台北站來作範例
影片中會有無限符號可以想成無法直接買到那站的車票 要轉車所以暫時是未知
票價圖
http://imgur.com/K7isTxw
先把台北站可以到達的票價都先列出來
http://imgur.com/FOe9ktS.jpg
這是從台北坐到各站的價錢
台北->南港再到各站的價錢 比對之後沒有比較便宜的 所以照抄下來
台北到南港已經是最便宜 用紅色底標註
http://imgur.com/JkfckeI.jpg
然後比對從台北->板橋 再到各站的價格有無較便宜
剛剛忘記放數據了 這裡開始會放 未標註地名的是代表台北到該站再到各站的價錢
像下圖是台北到板橋再到各站 (台北到板橋:40 + 板橋到各站:x)
有標註地名的是表示從哪一站過來的
http://imgur.com/jbwwya3.jpg
所以可以看到從台北直達還是都比較便宜
下一站 桃園
台北->桃園->各站
http://imgur.com/rFdOmkp.jpg
這裡可以看到某些站的價格已經打平了
不過打平還不夠
http://imgur.com/NbdF4Qy.jpg
下一站 新竹
台北->新竹->各站
http://imgur.com/fw24NFz.jpg
還是打平的狀態
下一站 苗栗
各位同胞們我們在台北->苗栗->嘉義終於省了10塊錢啦(用藍色標註
http://imgur.com/5ArhDaB.jpg
所以嘉義那邊地名改成苗栗 以後到嘉義都要先到苗栗轉車
苗栗忘記打出來了= ="
下一站 台中
還是打平 這邊要注意到嘉義都要在苗栗轉車 所以到嘉義路徑是
台北->苗栗->台中->嘉義
http://imgur.com/IY7W54s.jpg
下一站 彰化
還是一樣 數據忘記截= =" 抱歉
http://imgur.com/NRoNMMJ.jpg
下一站 雲林
http://imgur.com/KAKClN9.jpg
還4一樣
http://imgur.com/Pat5ivk.jpg
下一站 嘉義
由於前面知道 台北到嘉義在苗栗轉車會比較便宜 所以剩下的台南和高雄都會在苗栗轉車
也就是 台北->苗栗->嘉義->各站 這樣子
http://imgur.com/pMFUDvp.jpg
左營再便宜了10元
下一站 台南
http://imgur.com/qPVVWyR.jpg
沒有比較便宜
http://imgur.com/ouAOTQh.jpg
所以根據dijkstra's 演算法
台北->苗栗->嘉義->左營
這樣轉車到左營的確可以便宜20元
不過這是沒有考慮時間的問題
如果考慮進時間的話
相信絕對還是是台北高雄直達CP值最高的
在此做個簡單的介紹 有誤還請指正
如果變成考題學弟妹不要怪我030