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