单源最短路径问题的算法

Question

给出了一个有向图G= (V，E)，它具有正边权和负边权，但没有圈。设s∈V是给定的源顶点。如何找到一种算法，找到所有顶点的距离，肯定比Bellman Ford的O(VE)时间复杂度更快。

Answer 1

如果图没有圈，那么就可以按拓扑顺序处理顶点。

对于每个顶点v，如果它在距离d处是可到达的，那么对于重量w的每一个边(v，u)，用权重d+w标记u为可达的，如果u在较低的重量下已经可到达，那就别管它了。

因为你按拓扑顺序处理这个图，你知道当你处理一个顶点v时，你已经处理了它的所有前身，所以你会知道它的最短路径的长度。当然，第一个可到达的顶点是s。

在从s到的顶点子图上，很容易将它与卡恩算法结合起来进行拓扑排序。

1. 首先进行BFS搜索，以找到从s中可以到达的所有顶点，并同时计算该子集中每个顶点的传入边。
2. S将是计数'0‘的唯一顶点。它还有一个已知的从s到0的距离，把它放在一个队列中。
3. 当队列中有顶点时：
   1. 从队列中移除顶点v
   2. 调整与邻居的距离
   3. 减少它的邻居的传入边缘数。如果邻居的计数为0，则将其放入队列中。

当您完成时，所有可访问的顶点都将被处理，并且它们的所有距离都将被知道。