问题是找到从起始顶点到directed graph中所有其他顶点的最短路径。
但是图形将具有m positive加权边和k negative加权边，并且可以保证负加权边不会在一个循环中。换句话说，此图中没有负加权周期。
我试图直接使用Bellman-Ford和SPFA来解决这个问题，但是有没有更快的方法来做到这一点？
如果k足够大，你可能应该运行Bellman-Ford并称之为一天。
如果 k 很小，你可以借用 Johnson 算法中的重新加权技巧，但初始化速度比仅仅运行 Bellman-Ford 更快。回想一下，约翰逊为每个顶点计算一个潜在的π(v)，并将每个弧的成本从c(vw)调整到c′(vw)=c′(vw)=c(vw)−π(v)+π(w)，选择π，使c′无处为负。s 和 t 之间的最短路径相对于 c 与相对于 c′ 的最短路径相同，
假设输入图 G 正好有一个负弧，假设 c(xy) <0。使用 Dijkstra 算法计算从 y 到所有其他顶点的距离(以 G − xy 为单位)。然后定义 π(v) = 距离(y， v)。正确性证明遵循约翰逊算法的证明;弧 xy 不能是 y 的最短路径的一部分，因为没有负循环，因此 G - xy 上的 Dijkstra 实际上计算了 G 的最短路径树。
对于一般 k，我们可以递归地执行此操作。如果 k = 0，则运行 Dijkstra。否则，请删除负弧并递归计算最短路径，而不是使用 Dijkstra。一旦我们有了良好的π值，从给定的起始顶点再次运行 Dijkstra。
总运行时间为 O((k + 1) (m + n log n))，带有斐波那契堆。