鉴于以下问题:
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.
请注意权重函数在 Vertices 上，而不是在 Edges 上。 我在想的是更改 Bellman-Ford 算法并将 Relax 检查更改为以下内容:
1.if d[v]>d[u]+w[u]
1.1 d[v] <<-- d[u]+w[u]
1.2 PI[v] <<-- u
我认为这不够好，知道可能是什么问题吗？
谢谢，罗恩
最佳答案
让 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] 是顶点的最短路径。
关于algorithm - 在图中找到从 s 到所有顶点的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8909423/