K条负边--单源最短路径

Question

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

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

我真的想不出一个好的办法。

有什么建议吗？

Answer 1

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

然而，假设一个没有负环的有向图，你可以使用广度优先搜索，跟踪你已经遇到的负边和到目前为止你发现的每个节点的最短路径。如果您看到一个已经访问过的节点，那么只有在它比您以前访问的路径更好的情况下，才会再次访问该节点。

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