问一道题（groupon） - 未名空间MITBBS历史存档

M*l2013-02-12 08:02

1 楼

You are given a graph and an algorithm that can find the shortest path b/w
any two nodes
Now you have to find the second shortest path between same two nodes.
这个题怎么算呢？是说找出第一个点和其他所有点的最短距离，然后再合并其他所有点
和第二个点的最短距离，最后在里面找出第二小的？这样一共要call getShortestPath
() 2*(n-1)次。有没有更快的方法呢？
谢谢！

P*b2013-02-12 08:02

2 楼

只要有一条edge不一样就算另外一条path吗？

getShortestPath

【在 M******l 的大作中提到】

: You are given a graph and an algorithm that can find the shortest path b/w
: any two nodes
: Now you have to find the second shortest path between same two nodes.
: 这个题怎么算呢？是说找出第一个点和其他所有点的最短距离，然后再合并其他所有点
: 和第二个点的最短距离，最后在里面找出第二小的？这样一共要call getShortestPath
: () 2*(n-1)次。有没有更快的方法呢？
: 谢谢！

c*t2013-02-12 08:02

3 楼

把 the shortest path 上的 edge或者node 删一个，调用一次algorithm, 一个个试找
出最短的

getShortestPath

【在 M******l 的大作中提到】

: You are given a graph and an algorithm that can find the shortest path b/w
: any two nodes
: Now you have to find the second shortest path between same two nodes.
: 这个题怎么算呢？是说找出第一个点和其他所有点的最短距离，然后再合并其他所有点
: 和第二个点的最短距离，最后在里面找出第二小的？这样一共要call getShortestPath
: () 2*(n-1)次。有没有更快的方法呢？
: 谢谢！

M*l2013-02-12 08:02

4 楼

是说第二短路径和最短路径一定只有一条edge不一样吗？

【在 P*******b 的大作中提到】

: 只要有一条edge不一样就算另外一条path吗？
:
: getShortestPath

h*n2013-02-12 08:02

5 楼

看same node的one-hop neighbors 和另外一个node的最近距离?

getShortestPath

【在 M******l 的大作中提到】

: You are given a graph and an algorithm that can find the shortest path b/w
: any two nodes
: Now you have to find the second shortest path between same two nodes.
: 这个题怎么算呢？是说找出第一个点和其他所有点的最短距离，然后再合并其他所有点
: 和第二个点的最短距离，最后在里面找出第二小的？这样一共要call getShortestPath
: () 2*(n-1)次。有没有更快的方法呢？
: 谢谢！

M*l2013-02-12 08:02

6 楼

这个意思是说第二短路径和最短路径一定只有一个node或者edge不一样吗？
好像不一定？

【在 c********t 的大作中提到】

: 把 the shortest path 上的 edge或者node 删一个，调用一次algorithm, 一个个试找
: 出最短的
:
: getShortestPath

M*l2013-02-12 08:02

7 楼

嗯我是这么想的，就是不知道对不对，或者有没有更快的方法～

【在 h*****n 的大作中提到】

: 看same node的one-hop neighbors 和另外一个node的最近距离?
:
: getShortestPath

p*22013-02-12 08:02

8 楼

Buyiding

【在 M******l 的大作中提到】

: 这个意思是说第二短路径和最短路径一定只有一个node或者edge不一样吗？
: 好像不一定？

d*s2013-02-12 08:02

9 楼

你的意思是只看终点最近的一圈nodes，然后找出这些nodes里离起点倒数第二近的那个
吗？
这样做未必会让总体路径倒数第二近，因为它可能和第一近的路径都走了同一个节点（
离终点最近的那一圈里的那个）
我觉得楼上删除其他节点并比较的办法没问题，可以保证找到第二近的

getShortestPath

【在 M******l 的大作中提到】

: You are given a graph and an algorithm that can find the shortest path b/w
: any two nodes
: Now you have to find the second shortest path between same two nodes.
: 这个题怎么算呢？是说找出第一个点和其他所有点的最短距离，然后再合并其他所有点
: 和第二个点的最短距离，最后在里面找出第二小的？这样一共要call getShortestPath
: () 2*(n-1)次。有没有更快的方法呢？
: 谢谢！

c*t2013-02-12 08:02

10 楼

不是。不同路径即至少有一个 node or edge 不一样。你再想想。

★ 发自iPhone App: ChineseWeb 7.8

【在 M******l 的大作中提到】

: 这个意思是说第二短路径和最短路径一定只有一个node或者edge不一样吗？
: 好像不一定？

Y*Y2013-02-12 08:02

11 楼

删node肯定不行，因为第二条完全可以包括第一天条的所有节点。简单的例子就是三角
形，三边相同。去edge也有问题，因为第二条可以包括所有的边，比如中间某点多走一
个weight很小的圈也可以是第二条
这题条件不清楚，比如
second shortest path可不可以和shortest path长度相同？
有没negative edge? 如果有的话，就很麻烦，因为第二条可以和第一条经过的节点完
全相同，只是顺序不同。

【在 c********t 的大作中提到】

: 把 the shortest path 上的 edge或者node 删一个，调用一次algorithm, 一个个试找
: 出最短的
:
: getShortestPath

M*l2013-02-12 08:02

12 楼

不是最近一圈的nodes，我是想所有的nodes都找一遍

【在 d*s 的大作中提到】

: 你的意思是只看终点最近的一圈nodes，然后找出这些nodes里离起点倒数第二近的那个
: 吗？
: 这样做未必会让总体路径倒数第二近，因为它可能和第一近的路径都走了同一个节点（
: 离终点最近的那一圈里的那个）
: 我觉得楼上删除其他节点并比较的办法没问题，可以保证找到第二近的
:
: getShortestPath

S*t2013-02-12 08:02

13 楼

假设这两点是u, v，枚举剩下的点w，计算dist(u,w) + dist(w,v)，给出second
shortest就行了

getShortestPath

【在 M******l 的大作中提到】

: You are given a graph and an algorithm that can find the shortest path b/w
: any two nodes
: Now you have to find the second shortest path between same two nodes.
: 这个题怎么算呢？是说找出第一个点和其他所有点的最短距离，然后再合并其他所有点
: 和第二个点的最短距离，最后在里面找出第二小的？这样一共要call getShortestPath
: () 2*(n-1)次。有没有更快的方法呢？
: 谢谢！

Y*Y2013-02-12 08:02

14 楼

这个不行：
三角形：abc, ab: 3, ac: 1, bc 1:
a->b最短路径 a->c->b.
如果第二短路径的定义是可以和第一短相同的话，所有剩下的边(x,y), 计算dist(u,x)
+w(x,y)+dist(y,u)，找出最小。否则很难。

【在 S******t 的大作中提到】

: 假设这两点是u, v，枚举剩下的点w，计算dist(u,w) + dist(w,v)，给出second
: shortest就行了
:
: getShortestPath

c*t2013-02-12 08:02

15 楼

没有说算weight path吧，我理解是算distance最短

x)

【在 Y**Y 的大作中提到】

: 这个不行：
: 三角形：abc, ab: 3, ac: 1, bc 1:
: a->b最短路径 a->c->b.
: 如果第二短路径的定义是可以和第一短相同的话，所有剩下的边(x,y), 计算dist(u,x)
: +w(x,y)+dist(y,u)，找出最小。否则很难。

x*02013-02-12 08:02

16 楼

mark

h*n2013-02-12 08:02

17 楼

这能组成三角形麽。。。

x)

【在 Y**Y 的大作中提到】

: 这个不行：
: 三角形：abc, ab: 3, ac: 1, bc 1:
: a->b最短路径 a->c->b.
: 如果第二短路径的定义是可以和第一短相同的话，所有剩下的边(x,y), 计算dist(u,x)
: +w(x,y)+dist(y,u)，找出最小。否则很难。

p*n2013-02-12 08:02

18 楼

Assume the shortest path is of length N.
Call the shortest path algorithm for each node that is directly connected to
the source and record the lengths. Among these lengths, there should be one
(or some) equal to N-1, corresponding to the shortest path. If the next
smallest length is M. Then the answer is M+1.

getShortestPath

【在 M******l 的大作中提到】

: You are given a graph and an algorithm that can find the shortest path b/w
: any two nodes
: Now you have to find the second shortest path between same two nodes.
: 这个题怎么算呢？是说找出第一个点和其他所有点的最短距离，然后再合并其他所有点
: 和第二个点的最短距离，最后在里面找出第二小的？这样一共要call getShortestPath
: () 2*(n-1)次。有没有更快的方法呢？
: 谢谢！

s*12013-02-12 08:02

19 楼

用Bellman-ford
每次update时， update两项，就是最小和次小~
for i:=1 to |V|-1 do
for each edge(u,v) in E do
if(d[u][0]+w(u,v)tmp = d[v][0] //这个可能为次小项，记录
d[v][0]=d[u][0]+w(u,v)//更新最小项
min = min(tmp, d[u][1]+w(u,v)) //此时次小项有两个选择
d[v][1]=min //次小项也更新了
else //最小项没更新，次小项可能会更新
if(d[u][0]+w(u,v)d[v][1]=d[u][0] //次小项更新
应该行吧~

f*t2013-02-12 08:02

20 楼

dijkstra变形一下，每次update shortest和second shortest

x*92013-02-12 08:02

21 楼

果然只能这样

【在 f*******t 的大作中提到】

: dijkstra变形一下，每次update shortest和second shortest

l*h2013-02-12 08:02

22 楼

那么题目给了的条件（已有任何两点最小距离的function）还用不用？

【在 x******9 的大作中提到】

: 果然只能这样

c*p2013-02-12 08:02

23 楼

mark

m*n2013-02-12 08:02

24 楼

假设是从A到B，已知AB为最小路径。
第一，找到所有C，使得AC+CB=AB。这样的C是在AB的某条路径上。
从其他的节点找D使得AD+DB最小，那么这就是第二小路径。
如果第二小可以和第一小相等，那么如果存在AC+CB=AB，你就不
可能知道AB之间是否有连线，这个题无解。

getShortestPath

【在 M******l 的大作中提到】

: You are given a graph and an algorithm that can find the shortest path b/w
: any two nodes
: Now you have to find the second shortest path between same two nodes.
: 这个题怎么算呢？是说找出第一个点和其他所有点的最短距离，然后再合并其他所有点
: 和第二个点的最短距离，最后在里面找出第二小的？这样一共要call getShortestPath
: () 2*(n-1)次。有没有更快的方法呢？
: 谢谢！