[問題] second shortest path

看板Prob_Solve作者 (~"~)時間12年前 (2011/09/18 09:18), 編輯推噓5(5推 0噓 23→)
留言28則, 6人參與, 最新討論串1/1
請問要怎麼用dijkstra 找出 第二短的shortest path ? 邊可以重複用 沒有限制要simple 可以用dijkstra 做嗎？ 謝謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 58.115.165.34
推
09/18 12:13, , 1F
把所有path length在找的時候放到一個min heap, 找完後
09/18 12:13, 1F
→
09/18 12:13, , 2F
從min heap取兩個, 第二個就是了
09/18 12:13, 2F
→
09/18 12:14, , 3F
感覺不太對.0.0
09/18 12:14, 3F
→
09/18 12:15, , 4F
可給證明嗎？ 謝謝
09/18 12:15, 4F
→
09/18 12:58, , 5F
如果同時有兩個最短，例如三個path分別是5,5,6，
09/18 12:58, 5F
→
09/18 12:59, , 6F
你要的答案是 5 還是 6?
09/18 12:59, 6F
→
09/18 13:46, , 7F
6
09/18 13:46, 7F
→
09/18 13:54, , 8F
UVa 10342 - Always Late
09/18 13:54, 8F
→
09/18 13:57, , 9F
上面這題就是second shortest path的練習題。
09/18 13:57, 9F
→
09/18 13:57, , 10F
記得是好幾年前寫的，Floyd Warshall硬解。
09/18 13:57, 10F
→
09/18 14:06, , 11F
我就是在寫這題-.- 有看到Warshall得解法
09/18 14:06, 11F
→
09/18 14:07, , 12F
但演算法筆記上面寫有Dijkstra 得解法
09/18 14:07, 12F
→
09/18 14:07, , 13F
想知道怎麼做
09/18 14:07, 13F
推
09/18 14:13, , 14F
我...我...是用 floyd warshall 做的 >///<
09/18 14:13, 14F
推
09/18 14:59, , 15F
找到 shortest path 之後，刪掉 shortest path 的一邊
09/18 14:59, 15F
→
09/18 14:59, , 16F
再找 shortest path，有可能就是 second shortest path
09/18 14:59, 16F
→
09/18 14:59, , 17F
shortest path 上每條邊刪掉一次、找 shortest path
09/18 14:59, 17F
→
09/18 15:00, , 18F
照理說應該有答案，只是萬一所得到的答案都跟原來一樣長
09/18 15:00, 18F
→
09/18 15:00, , 19F
怎麼辦呢？sorry，可能是我沒想清楚。
09/18 15:00, 19F
→
09/18 15:02, , 20F
我一開始寫的是這樣 但這樣找的是simple path
09/18 15:02, 20F
推
09/19 08:42, , 21F
每條邊的長度若都是正的的話
09/19 08:42, 21F
→
09/19 08:43, , 22F
可以先寫一個不限制simple path的shortest path的演算法
09/19 08:43, 22F
→
09/19 08:44, , 23F
然後找起點的每個鄰居到終點的 shortest path
09/19 08:44, 23F
→
09/19 08:45, , 24F
再加上前面的做法，好像會包含 second shortest path
09/19 08:45, 24F
→
09/19 08:45, , 25F
不過不太確定...
09/19 08:45, 25F
→
09/19 08:46, , 26F
最近好像都只在想 heuristic 的方法，沒有好的證明...
09/19 08:46, 26F
推
09/22 14:02, , 27F
http://ppt.cc/KnwA 第三節有講到有向圖的演算法
09/22 14:02, 27F
→
09/22 14:07, , 28F
四
09/22 14:07, 28F
‣ 更多 singlovesong 的文章
文章代碼(AID): #1ETKR-fl (Prob_Solve)