小弟學店資工系 簡單介紹一下這個演算法
作者在文中已經有提到是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
作者:
shiburin (廢文製造機)
2017-08-15 14:32:00嗯跟我想的一樣
作者:
mcmcmc (mcmcmc)
2017-08-15 14:34:00操作不難 難的是證明為何是對的
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 14:34:00高鐵路線基本上只是一條鍊 看不出Dijkstra's的特點
作者:
seuil ( )
2017-08-15 14:35:00演算法厲害 可以算出便宜20元 跟我用紙筆算的一樣
作者:
wemee (方天畫)
2017-08-15 14:35:00樓下跳針貪婪法則跟旅行背包解高鐵問題
作者:
hipab (嗨趴)
2017-08-15 14:40:00樓下負cycle shortest path 讓高鐵無限迴圈
作者:
fate201 (Licht)
2017-08-15 14:52:00每條路的票價當成距離就好了 最終移動距離都相同啊
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 14:53:00樓上 你有聽過最短路徑樹嗎還一張網勒...
…台北到台中，台中再到高雄，和台北到高雄是三條線講這樣夠白了吧…
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 14:56:00不是很明白你想表達什麼 Dijkstra's只會留下到某個點
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 14:57:00這求的是單源最短路徑 我想你指的是all pairs
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 15:00:003樓? 你現在是在想證明嗎
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 15:02:00這樣說好了 假設a到b有5種相異路徑 成本不盡相同演算法跑完 只會留下一種成本最低的路徑 其他的都不管單源最短路徑的情況下啦假設起點就是a 那Dijkstra's一旦走到了b 走法肯定是成本最低 所以之後再有路徑可以到b都無視 因為不會改善a到b 或是a經過b到其他點的距離在一條鍊的情況下這看不出來 因為只會一直往前鑽
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 15:08:00哦應該說我錯了 這不算是一條鍊 因為各站間可以直達我誤會你了 你是對的
作者:
Cybershit (BMI<18der肥宅)
2017-08-15 15:09:00所以原圖的確是一張網 不是一條鍊
作者: zzzz8931 (肥宅) 2017-08-15 15:18:00
時間複雜度？