為什麼這篇dijkstra演算法筆記鄉民發文收入到精華區：因為在dijkstra演算法筆記這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者singlovesong (~"~)看板Prob_Solve標題[問題] second ...
請問要怎麼用dijkstra 找出 第二短的shortest path ?
邊可以重複用 沒有限制要simple
可以用dijkstra 做嗎？
謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.115.165.34
推 shaopin:把所有path length在找的時候放到一個min heap, 找完後 09/18 12:13
→ shaopin:從min heap取兩個, 第二個就是了 09/18 12:13
→ singlovesong:感覺不太對.0.0 09/18 12:14
→ singlovesong:可給證明嗎？ 謝謝 09/18 12:15
→ tkcn:如果同時有兩個最短，例如三個path分別是5,5,6， 09/18 12:58
→ tkcn:你要的答案是 5 還是 6? 09/18 12:59
→ singlovesong:6 09/18 13:46
→ bleed1979:UVa 10342 - Always Late 09/18 13:54
→ bleed1979:上面這題就是second shortest path的練習題。 09/18 13:57
→ bleed1979:記得是好幾年前寫的，Floyd Warshall硬解。 09/18 13:57
→ singlovesong:我就是在寫這題-.- 有看到Warshall得解法 09/18 14:06
→ singlovesong:但演算法筆記上面寫有Dijkstra 得解法 09/18 14:07
→ singlovesong:想知道怎麼做 09/18 14:07
推 DJWS:我...我...是用 floyd warshall 做的 >///< 09/18 14:13
推 springman:找到 shortest path 之後，刪掉 shortest path 的一邊 09/18 14:59
→ springman:再找 shortest path，有可能就是 second shortest path 09/18 14:59
→ springman:shortest path 上每條邊刪掉一次、找 shortest path 09/18 14:59
→ springman:照理說應該有答案，只是萬一所得到的答案都跟原來一樣長 09/18 15:00
→ springman:怎麼辦呢？sorry，可能是我沒想清楚。 09/18 15:00
→ singlovesong:我一開始寫的是這樣 但這樣找的是simple path 09/18 15:02
推 springman:每條邊的長度若都是正的的話 09/19 08:42
→ springman:可以先寫一個不限制simple path的shortest path的演算法 09/19 08:43
→ springman:然後找起點的每個鄰居到終點的 shortest path 09/19 08:44
→ springman:再加上前面的做法，好像會包含 second shortest path 09/19 08:45
→ springman:不過不太確定... 09/19 08:45
→ springman:最近好像都只在想 heuristic 的方法，沒有好的證明... 09/19 08:46
→ DJWS: 四 09/22 14:07