algorithm - 您可以对图形进行哪些修改以允许 Dijkstra 算法对其进行处理？

Question

所以我一直在想，在不求助于其他算法的情况下，您可以对图形进行哪些修改以允许 Dijkstra 算法对其进行处理，并在一天结束时仍然得到正确答案？如果有可能呢？

我首先想到的是向所有权重添加一个等于最负权重的常数，但我发现这会弄乱一切并改变原始的单一源路径。

然后，我想到遍历图，将所有小于零的权重放入数组或类似的东西中，然后将其乘以-1。我认为他的方法可行(忽略运行时间限制)，但也许我看错了方向。

编辑:另一个想法。如何将所有负权重永久设置为无穷大。这样可以确保它们被忽略？

所以我只是想听听一些关于这个的意见；大家怎么看？

Answer 1

您似乎在寻找类似于 Johnson's 的内容算法:

1. First, a new node q is added to the graph, connected by zero-weight edges to each of the other nodes.

2. Second, the Bellman–Ford algorithm is used, starting from the new vertex q, to find for each vertex v the minimum weight h(v) of a path from q to v. If this step detects a negative cycle, the algorithm is terminated.

3. Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from u to v, having length w(u,v), is given the new length w(u,v) + h(u) − h(v).

4. Finally, q is removed, and Dijkstra's algorithm is used to find the shortest paths from each node s to every other vertex in the reweighted graph.

通过任何算法，您都应该检查负循环，如果没有负循环，则找到最短路径。

在您的情况下，您需要运行 Dijkstra 算法一次。另请注意，在 Johnson 的算法中，semi Bellman–Ford 算法仅针对新添加的节点运行。 (不是所有顶点)。