作者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