→ seafox5566: 1f帥08/15 14:32
推 shiburin: 嗯跟我想的一樣08/15 14:32
推 mcmcmc: 操作不難 難的是證明為何是對的08/15 14:34
J個小弟還真沒學過 我只會驗算
→ Cybershit: 高鐵路線基本上只是一條鍊 看不出Dijkstra's的特點08/15 14:34
的確 可是我想不到什麼好例子 要我算公車我會算到死
推 seuil: 演算法厲害 可以算出便宜20元 跟我用紙筆算的一樣08/15 14:35
推 wemee: 樓下跳針貪婪法則跟旅行背包解高鐵問題08/15 14:35
推 hipab: 樓下負cycle shortest path 讓高鐵無限迴圈08/15 14:40
※ 編輯: orz8809ed (174.22.7.165), 08/15/2017 14:44:38
→ end81235: 在說什麼啊，每條路的成本不同，要看成不同的路啊08/15 14:49
不同的路都有算出來成本 如果沒有比較便宜就沿用原本的 像一開始到左營是直達 最後到?
社?
※ 編輯: orz8809ed (174.22.7.165), 08/15/2017 14:54:03
推 fate201: 每條路的票價當成距離就好了 最終移動距離都相同啊08/15 14:52
→ end81235: 和一條鍊有什麼關係？路徑畫出來就是一張網08/15 14:52
的確權重畫出來是一張網
一條鏈指的是高鐵實際上是一條路線
→ Cybershit: 樓上 你有聽過最短路徑樹嗎 08/15 14:53
→ Cybershit: 還一張網勒...08/15 14:53
→ end81235: …台北到台中，台中再到高雄，和台北到高雄是三條線08/15 14:54
→ end81235: 講這樣夠白了吧…08/15 14:54
我這裡沒有把所有權重畫出來
所有權重有66個
大大有耐心畫出來的話會非常感謝XD
※ 編輯: orz8809ed (174.22.7.165), 08/15/2017 15:00:13
→ Cybershit: 不是很明白你想表達什麼 Dijkstra's只會留下到某個點 08/15 14:56
→ end81235: 最短路徑樹是說，由某一個起點的角度來看的結果 08/15 14:56
→ Cybershit: 點的最佳路徑的成本當作代表 08/15 14:56
→ end81235: 和高鐵是直的是彎的，有沒有分枝沒有關係 08/15 14:57
→ Cybershit: 這求的是單源最短路徑 我想你指的是all pairs 08/15 14:57
→ end81235: 我是在說，無論高鐵路線長怎樣，只要a站到b站的成本不同 08/15 14:57
→ end81235: 就要看成不同的路徑 08/15 14:57
→ end81235: 因為這裡的權重是票價，不是距離，也不是物理上的路徑 08/15 14:58
→ end81235: 還是我有誤解三樓那句的意思？ 08/15 14:59
→ Cybershit: 3樓? 你現在是在想證明嗎 08/15 15:00
→ end81235: 4樓啦，看錯 08/15 15:01
→ Cybershit: 這樣說好了 假設a到b有5種相異路徑 成本不盡相同 08/15 15:02
→ Cybershit: 演算法跑完 只會留下一種成本最低的路徑 其他的都不管 08/15 15:03
→ Cybershit: 單源最短路徑的情況下啦 08/15 15:03
→ Cybershit: 假設起點就是a 那Dijkstra's一旦走到了b 走法肯定是成 08/15 15:04
→ Cybershit: 本最低 所以之後再有路徑可以到b都無視 因為不會改善 08/15 15:04
→ Cybershit: a到b 或是a經過b到其他點的距離 08/15 15:04
→ Cybershit: 在一條鍊的情況下這看不出來 因為只會一直往前鑽 08/15 15:05
高鐵畫出來的圖大概長這樣
http://imgur.com/dNIZbaz.jpg
相對於非每點互聯的圖形
http://imgur.com/yeOYQGv.jpg
高鐵圖的確比較難顯現出dijkstra's的特性
※ 編輯: orz8809ed (174.22.7.165), 08/15/2017 15:09:51
→ end81235: …… 08/15 15:08
→ Cybershit: 哦應該說我錯了 這不算是一條鍊 因為各站間可以直達 08/15 15:08
→ Cybershit: 我誤會你了 你是對的 08/15 15:09
→ end81235: 感謝原po補充 08/15 15:09
→ Cybershit: 所以原圖的確是一張網 不是一條鍊 08/15 15:09
→ end81235: 不會，互相討論 08/15 15:10