对于包含多个源的图，我们可以使用Bellman-ford算法吗

Question

我们知道，我们可以对包含多个源的图使用Dijkstra算法。例如，这个问题可以通过对多个源使用多个Dijkstra's算法来解决。同样，我们能实施吗Bellman-ford算法？如果可能的话，共享伪代码。

假设该图包含负权重边，并且没有负循环。

Answer 1

当然！一种简单的方法是将具有多个源的原始图转换为仅具有一个源的新图。只需在原始图的每个源中添加一个具有零成本定向边的新节点s。从这个新节点开始运行Bellman-Ford，然后有效地模拟从每个源开始寻找最短路径。