负权指的是一张图中包含一条权重小于0的边。负环指的是一张图中存在权重只和为负数的环。如果一张图中存在负环，那么这张图是没有最短路径的。

那么，假设图中不存在负环，但是有负权，那么最短路径如何求解呢？答案就是使用Bellman-Ford算法，该算法的性能一般。

基本思想

Bellman-Ford算法的基本思想就是对图中所有的边都进行V次“放松”操作。所以该算法的复杂度是E×V。

该算法的计算过程如下图所示。

改进

实际应用中会对算法进行改进。改进方法就是用队列记录发生变化的顶点，这样能减少平均复杂度，但是无法减少最坏情况下的复杂度。

代码

public class BellmanFordSP extends SP {
    public BellmanFordSP(EdgeWeightedDigraph G, int s) {
        super(G, s);
 
        // 将所有顶点到原点的距离设为无穷大
        // 注意：下面这段代码不要遗漏
        for(int i=0;i<G.V();i++){
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        distTo[s] = 0;
 
        for(int i=0;i<G.V();i++){
            for(int v=0;v<G.V();v++){
                for(DirectedEdge e:G.adj(v)){
                    relax(e);
                }
            }
        }
    }
}

算法总结

无环有负权，使用拓扑排序算法，复杂度为E+V

有环无负权，使用Dijkstra算法，复杂度为E logV

有环有负权，使用Bellman-Ford算法，复杂度为E V

应用

炒汇

下表展示了个币种之间的汇率情况。如果不考虑交易的手续费，汇率价格不变，那么可以从图中找出一条循环赚钱的路径，这个路径就是通过寻找负环得出的。

arbitrage opportunity

算法8-11：最短路径算法之负权,布布扣,bubuko.com

算法8-11：最短路径算法之负权

原文：http://blog.csdn.net/caipeichao2/article/details/34920721