查找图中从 s 到所有顶点的最短路径
鉴于以下问题：
给定有向图 G=(V,E) 和权重函数 W:V→R ，描述一个算法 找到从 S 到所有其他顶点的最短路径，其中 路径等于所有顶点的总和。您需要更改现有算法， 为了实现这一点，所以不需要编写新的算法。
请注意，权重函数位于“顶点”上，而不是（！！）位于“边”上。 我的想法是更改 Bellman-Ford 算法并将 Relax 检查更改为以下内容：
1.if d[v]>d[u]+w[u]
1.1 d[v] <<-- d[u]+w[u]
1.2 PI[v] <<-- u
我认为这不够好，知道可能是什么问题吗？
谢谢，罗恩
Given the following problem :
Given the directed graph G=(V,E) with the weight function W:V→R , describe an algorithm
that find the shortest paths from S to all other Vertices , where the length of the
path equals to the SUM of all the vertices.You need to change an existing algorithm ,
to make that work , so there's no need to write a new algorithm.
Please notice that the weight function is on the Vertices and NOT(!!) on the Edges .
What I was thinking is to change the Bellman-Ford algorithm and change the Relax check to the following :
1.if d[v]>d[u]+w[u]
1.1 d[v] <<-- d[u]+w[u]
1.2 PI[v] <<-- u
I don't think this works good enough , any idea what might be the problem ?
thanks ,Ron
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
让
w:V->R为你的权重函数。创建权重函数：
w':E->R，如下所示：w'(u,v) = w(v)使用 w 运行 dijkstra/bellman-ford '。令 d'[v] 为根据 w' 到 v 的最小路径权重。
那么如果最短路径是
s->u1->u2->...->un->v，则得到：d'[v] = w '(s,u1) + w'(u1,u2) + ... + w'(un,v)[根据 dijkstra/bellman fofrd 的正确性]，因此d'[v] = w(u1) + w(u2) + ... + w(un) + w(v)[根据 w' 的定义]。因此，总的来说，您得到： d[v] = w(s) d'[v] 并且 d[v] 是顶点的最短路径。
let
w:V->Rbe your weight function.Create a weightening function:
w':E->Ras follows:w'(u,v) = w(v)Run dijkstra/bellman-ford with w'. let d'[v] be the minimal path's weight to v, according to w'.
Then if the shortest path is
s->u1->u2->...->un->v, you get:d'[v] = w'(s,u1) + w'(u1,u2) + ... + w'(un,v)[by correctness of dijkstra/bellman fofrd] and thusd'[v] = w(u1) + w(u2) + ... + w(un) + w(v)[by definition of w'].so, at overall you get:
d[v] = w(s) d'[v]and d[v] is the shortest path for vertices.我认为 Floyd–Warshall_algorithm 是最好的起点。当然，维基百科今天已关闭以示抗议:)。
I think the Floyd–Warshall_algorithm is the best starting point. Of course, Wikipedia is down in protest today :).