问个求SPFA的问题 - Vijos

问答
mymymy LV 10 @ 2009-03-24 09:27:45

怎样求第K短路？

wushinoi LV 10 @ 2009-03-24 09:27:45

.

无意义
gnaggnoyil LV 10 @ 2009-03-22 18:10:24

就是没完没了地合并优先队列

RT
mymymy LV 10 @ 2009-03-22 17:57:37

??听不懂

我好菜......
ipip2005 LV 10 @ 2009-03-21 22:42:35

楼上的方法就是维护K优解,复杂度就是求最短路复杂度再乘个K
gnaggnoyil LV 10 @ 2009-03-21 20:46:09

存个每个点前k优解的优先队列

RT.原来的松弛就变成优先队列的合并.

---|---|---|---|---|---|---|---|---|-

不一定对的说.
mymymy LV 10 @ 2009-03-21 20:00:06

那是第2短路

要更一般的。
gnaggnoyil LV 10 @ 2009-03-21 18:06:26

枚举断开每个最短路径的边,再最短路,