algorithm - K 个负边 - 单源最短路径

Question

我已经使用 dijkstra 解决了在只有一个负边时找到所有单源最短路径的问题。

现在我正试图面对一个新问题，如何仅使用 dijkstra(不是 bellman ford)在恰好有 K 个负边时从给定源找到所有最短路径。 (k 已知)。

实在想不出什么好办法。

有什么建议吗？

Answer 1

如果它是一个无向图，则没有单一的最短路径，因为即使只有一个负边，你也可以在该负边上来回走动，并有无数条负无穷大的路径。

但是，假设有向图没有负环，您可以使用广度优先搜索并跟踪您已经到达的负边和到目前为止您发现的每个节点的最短路径。如果你看到一个你已经访问过的节点，你只会再次去那里，如果它比你以前到达那里的路径更好的话。

由于没有负循环，算法必须终止。算法终止后，目标节点应该有到达那里的最佳路径。