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

Question

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

现在我正试图面对一个新问题，当仅使用dijkstra（不是bellman ford）时，如何找到来自给定源的所有最短路径。(k 是已知的)。

实在想不出好办法。

有什么建议么？

Answer 1

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

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

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