Bellman Ford - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

贝尔曼-福特算法(Bellman–Ford algorithm)油管最好的三个讲解
图解贝尔曼-福特算法

详解

算法/最短路径/Bellman-Ford贝尔曼福特算法
深入理解Bellman-Ford（SPFA）算法

松弛Relax操作

通俗解释：想像图论中的graph是用毛线和珠子组成的网状结构，两颗珠子之间毛线的长度即edge上的权值，一开始十分松乱的放在桌上。 现在你要求SSP（单源最短路），当发现从源点s到当前点v有两条路径，relax操作可以想象成用力把s和v两点往外撑开。这时候依照生活经验，我们可以很自然的看到s点和v点之间较短的那条边处于紧绷状态，而较长的那条边处于松弛状态。因此非常形象的把这个操作称为松弛操作。

如下图，松弛结点v和结点w之间的边

graph

负权环

  • 定义：源点到源点的一个环，环上权重和为负数
  • 影响：负权环会导致算法在求最短路径时进入死循环，环上的各个结点的最短路径都可以无限缩小
  • 图例：如下图所示以V3为源点的负权环
graph

标准写法

松弛操作

private void relax(int v, int w) {
    // dist[v]：结点s到结点v的距离
    // dist[w]：结点s到结点w的距离
    // 若结点s到结点v的距离 > 结点s到结点w的距离 + 结点v和结点w的距离
    // 即 s -> v > s -> w + w -> v
    if (dist[v] > dist[w] + weight(v, w)) {
        // 设置结点s到结点v的距离 = 结点s到结点w的距离 + 结点v和结点w的距离
        // 即 s -> v = s -> w + w -> v
        dist[v] = dist[w] + weight(v, w);
    }
}

核心部分（松弛所有的边）

public void bellmanFord() {
    // 源点的距离为0
    dist[srcIndex] = 0;
    // 从源点开始
    for (int i = 0; i < adjList.size(); i++) {
        // 源点的位置不一定是第一个结点，因此一次遍历不一定能松弛所有的边
        // 例如 dist[MAX_VALUE, MAX_VALUE, MAX_VALUE, ..., 0];
        // 此时源点是最后一个结点，那么前面的全部结点的初始值都是Integer.MAX_VALUE
        // 遍历前面的全部结点时都不会进行松弛操作
        // 因此需要多套一层遍历在外面，确保所有的边都完成松弛操作
        for (int j = 0; j < adjList.size(); j++) {
            ArrayList<AdjListNode> list = adjList.getNodes().get(j).getRoot();
            for (int k = 0; k < list.size(); k++) {
                relax(list.get(k).getIndex(), j, list.get(k).getWeight());
            }
        }
    }
}

完整代码

public class BellmanFord<T> {

    // 源点的下标
    private int srcIndex;
    // 源点到每一条边的距离
    private int[] dist;
    private AdjacencyList<T> adjList;

    public BellmanFord(int srcIndex, AdjacencyList<T> adjList) {
        this.srcIndex = srcIndex;
        this.adjList = adjList;
        this.dist = new int[adjList.size()];
        // 初始化源点到其它顶点之间的距离为无穷大
        Arrays.fill(dist, Integer.MAX_VALUE);
    }

    private void relax(int i, int j, int w) {
        // Integer.MAX_VALUE + 任何值都会变成负数
        if (dist[j] == Integer.MAX_VALUE) {
            return;
        }
        if (dist[i] > dist[j] + w) {
            dist[i] = dist[j] + w;
        }
    }

    private boolean isRelax(int i, int j, int w) {
        // Integer.MAX_VALUE + 任何值都会变成负数
        if (dist[j] == Integer.MAX_VALUE) {
            return false;
        }
        return dist[i] > dist[j] + w;
    }

    public void bellmanFord() {
        // 源点的距离为0
        dist[srcIndex] = 0;
        // 从源点开始
        // 优化：这层遍历只是确保所有的边都完成松弛操作，如果某次遍历没有再进行松弛操作，
        // 代表所有的松弛操作都已经完成，可以跳出循环
        for (int i = 0; i < adjList.size(); i++) {
            // 源点的位置不一定是第一个结点，因此一次遍历不一定能松弛所有的边
            // 例如 dist[MAX_VALUE, MAX_VALUE, MAX_VALUE, ..., 0];
            // 此时源点是最后一个结点，那么前面的全部结点的初始值都是Integer.MAX_VALUE
            // 遍历前面的全部结点时都不会进行松弛操作
            // 因此需要多套一层遍历，确保所有的边都完成松弛操作
            for (int j = 0; j < adjList.size(); j++) {
                ArrayList<AdjListNode> list = adjList.getNodes().get(j).getRoot();
                for (int k = 0; k < list.size(); k++) {
                    relax(list.get(k).getIndex(), j, list.get(k).getWeight());
                }
            }
        }
    }

    // 判定负权环
    private boolean negativeWeightCycleExist() {
        // 对每个结点的路径更新后，若图中不存在负权环则无法再缩减距离
        // 遍历所有的边，若第n次操作仍然可以进行松弛操作，则说明存在负权环
        for (int i = 0; i < adjList.size(); i++) {
            ArrayList<AdjListNode> list = adjList.getNodes().get(i).getRoot();
            for (int j = 0; j < list.size(); j++) {
                if (isRelax(list.get(j).getIndex(), i, list.get(j).getWeight())) {
                    return true;
                }
            }
        }
        return false;
    }

    public void print() {
        if (negativeWeightCycleExist()) {
            System.out.println("存在负权环！");
        } else {
            System.out.print("最短距离： ");
            for (int i = 0; i < dist.length; i++) {
                System.out.print(dist[i] + " ");
            }
            System.out.println();
        }
    }
}

测试

图1 图2 图3
graph graph graph 
ArrayList<Node<String>> nodes = new ArrayList<>();
nodes.add(new Node<String>("V1"));
nodes.add(new Node<String>("V2"));
nodes.add(new Node<String>("V3"));
nodes.add(new Node<String>("V4"));
nodes.add(new Node<String>("V5"));
nodes.add(new Node<String>("V6"));
nodes.add(new Node<String>("V7"));
nodes.add(new Node<String>("V8"));

// 图1
AdjacencyList<String> adjList1 = new AdjacencyList<String>(nodes);
adjList1.addEdge(0, 1, 2);
adjList1.addEdge(0, 2, 7);
adjList1.addEdge(1, 3, 3);
adjList1.addEdge(2, 5, 5);
adjList1.addEdge(2, 6, 10);
adjList1.addEdge(3, 7, 6);
adjList1.addEdge(4, 1, 8);
adjList1.addEdge(4, 7, 4);
adjList1.addEdge(5, 6, 1);

BellmanFord<String> bellmanFord1 = new BellmanFord<String>(0, adjList1);
bellmanFord1.bellmanFord();
bellmanFord1.print();
// 最短距离： 0 2 7 5 2147483647 12 13 11

// 图2
AdjacencyList<String> adjList2 = new AdjacencyList<String>(nodes);
adjList2.addEdge(0, 1, 2);
adjList2.addEdge(0, 2, 7);
adjList2.addEdge(1, 3, 8);
adjList2.addEdge(1, 4, -3);
adjList2.addEdge(2, 5, 5);
adjList2.addEdge(2, 6, 1);
adjList2.addEdge(3, 7, -4);
adjList2.addEdge(4, 7, 6);
adjList2.addEdge(5, 6, 10);

BellmanFord<String> bellmanFord2 = new BellmanFord<String>(0, adjList2);
bellmanFord2.bellmanFord();
bellmanFord2.print();
// 最短距离： 0 2 7 10 -1 12 8 5

// 图3
AdjacencyList<String> adjList3 = new AdjacencyList<String>(nodes);
adjList3.addEdge(0, 1, 2);
adjList3.addEdge(0, 2, 7);
adjList3.addEdge(1, 3, 8);
adjList3.addEdge(1, 4, -3);
adjList3.addEdge(2, 5, -5);
adjList3.addEdge(3, 7, -4);
adjList3.addEdge(4, 7, 6);
adjList3.addEdge(5, 6, -2);
adjList3.addEdge(6, 2, 1);

BellmanFord<String> bellmanFord3 = new BellmanFord<String>(0, adjList3);
bellmanFord3.bellmanFord();
bellmanFord3.print();
// 存在负权环！

要点

  • E条边，V个结点，时间复杂度是O(EV)
⚠️ **GitHub.com Fallback** ⚠️