最短路径算法

本文讲解图中点与点之间的最短路径问题，主要讲解三个算法：

Dijkstra 算法
Bellman-Ford 算法
Floyed 算法

其中 Dijkstra 与 Bellman-Ford 是解决单源最短路径问题，即它只能求解某节点到其他节点的最短路径，而 Floyed 算法能够求解所有节点之间的最短路径。

Dijkstra 算法

Dijkstra 算法它能够求解单源最短路径问题，并且使用该算法有一个前提，图中不能存在负权边，即图中的每条边的权值都必须是大于等于 0 的。

Dijkstra 算法使用一个 dis 数组来表示从源 s 到其他节点的最短距离，例如 dis[v] 表示的就是源 s 到达节点 v 的最短距离，在初始时，除了 dis[s] 为 0，其余的 dis[v] 均为无穷大。

Dijkstra 算法的思想是，每次从未遍历的节点，寻找在 dis 数组中值最小的节点，然后根据这个节点更新其未被遍历过的相邻节点在 dis 数组中的值。例如遍历到节点 v，其相邻节点为 w，并且节点 w 未被遍历过，如果 dis[v] + weight(v,w) < dis[w]，那么就更新 dis[w]，其中 weight(v, w) 是边 v-w 的权值。

举个例子，假设源为节点 0，我们求解节点 0 到各个节点的最短路径

初始节点 0 到节点 0 的距离为 0，其余节点距离节点 0 的距离为 $\infin$。根据 Dijkstra 算法，每次从未遍历的节点，寻找在 dis 数组中值最小的节点，所以此时我们找到了节点 0，dis[0] 为 0，比其他元素小。我们来到节点 0，根据公式 dis[0] + weight(0, w) < dis[w]更新与 0 相邻的节点 w

继续从未遍历的节点，寻找在 dis 数组中值最小的节点，是节点 2，它的值为 1，并且此时我们可以断定节点 0 离节点 2 的最短距离就是 1。

为什么呢? 假设存在一条更短的路径从 0 到 2，例如是 0-1-2，但是因为此时 0-2 是最小的，而图中又不存在负权边，所以 0-1-2 比 0-1 还大，也就是比 0-2 大，所以 0-2 就是从 0 到 2 的最短路径。来到节点 2 之后，根据条件 dis[2] + weight(2, w) < dis[w] 是否成立更新其相邻节点。

继续从未遍历的节点，寻找在 dis 数组中值最小的节点，此时 dis[1] 与 dis[6] 的值都是 2，随便选一个就可以，这里我选择节点 1，并且此时可以判定节点 0 到节点 1 的最短路径就是 dis[1] 为 2。为什么?

假设存在一条路径经过未遍历的节点从 0 到达节点 1，比如是节点 4 好了，因为 dis[1] 此时是未遍历的节点中最小的，所以 dis[1] < dis[4]，更别说还要加上节点 4 到节点 1 的距离，矛盾，所以找不到一条经过未遍历节点来到节点 1。

那么是否存在一条路径只经过已经遍历过的节点到达节点 1，并且路径比 dis[1] 小，不妨假设存在这么一条路径 0 -> ... -> s -> 1，它的值比 dis[1] 小，即 dis[s] + weight(s, 1) < dis[1]，那么当我们之前遍历到节点 s 对相邻节点更新的时候就会更新 dis[1] 为更小的值，也产生了矛盾，因此也不存在一条路径只经过已经遍历过的节点到达节点 1。所以我们可以说此时的 dis[1] 就是从 0 到 1 的最短路径。

来到节点 1 之后，更新其未被遍历过的相邻节点的值，当然图中节点 1 此时不存在未被遍历过的相邻节点，所以不进行任何的更新

继续从未遍历的节点，寻找在 dis 数组中值最小的节点，找到节点 6，此时 dis[6] 的值为 2，并且此时我们可以判定从节点 0 到节点 6 的最短距离就是 2。

分析方法同上，先假设存在一条从未被遍历过的节点到达节点 6 得到的更短路径，但是因为 dis[6] 已经是从 0 到未被遍历的节点最小的，图中又不存在负权边，所以矛盾，再做假设存在只经过已被遍历过的节点到达节点 6，那么在之前 dis[6] 的值就会被更新为更小的值，也会产生矛盾，从而得到结论，不存在另外一条路径从 0 到 6 更短，此时 dis[6] 就是从 0 到 6 的最短距离。

来到节点 6 之后根据条件更新其未被遍历的相邻节点，图中节点 6 不存在未被遍历过的相邻节点，因此不作更新

继续从未遍历的节点，寻找在 dis 数组中值最小的节点，发现 dis[3] 和 dis[4] 都是 3，我们就随便选择一个，这里选择节点 3，并且此时可以判定 dis[3] 是从节点 0 到节点 3 的最短距离，已经分析过多次，不再分析。

来到节点 3 之后，根据条件更新其未被遍历过的相邻节点，与节点 3 相邻未被遍历过的节点就是节点 4，但是并不满足 dis[3] + 3 < dis[4] 的条件，所以不更新 dis[4]

重复上面的过程，我们可以得到下面这张表

	0	1	2	3	4	5	6
dis	0	2	1	3	3	4	2

第二行的值表示原点到各点的最短路径。

所以 Dijkstra 算法就始终在重复两步：

寻找未被遍历节点中在 dis 数组中最小的那个节点
根据条件更新未被遍历过的相邻节点

寻找最小节点的操作我们使用一个优先队列来完成，直接从队首取出的值就是最小的，无需寻找

import java.util.*;

public class Dijkstra {
    private WeightedGraph graph;
    private int s;
    private int[] dis;
    private boolean[] visited;
    // 求具体的路径用
    private int[] pre;

    public Dijkstra(WeightedGraph graph, int s) {
        this.graph = graph;
        graph.validateVertex(s);
        this.s = s;

        this.dis = new int[graph.V()];
        this.visited = new boolean[graph.V()];
        this.pre = new int[graph.V()];

        // 初始化操作
        Arrays.fill(pre, -1);
        Arrays.fill(dis, Integer.MAX_VALUE);

        pre[s] = s;
        dis[s] = 0;

        // 建立一个优先队列，Node 保存的是节点 dis[v] 的值
        PriorityQueue<Node> queue =
                new PriorityQueue<>((node1, node2) -> node1.getDis() - node2.getDis());
        queue.add(new Node(s, 0));
        while (!queue.isEmpty()) {

            // 选出最小节点
            int v = queue.remove().getV();

            // 可能存在重复添加的情况，忽略
            if (visited[v]) {
                continue;
            }
            visited[v] = true;

            // 更新未被遍历的相邻节点
            for (int w: graph.adj(v)) {
                if (!visited[w]) {
                    dis[w] = Math.min(dis[w], dis[v] + graph.getWeight(v, w));
                    // 将 dis[w] 添加进队列，可能会重复添加
                    // 不过我们只对最小的那个感兴趣，重复添加取出后会被忽略
                    queue.add(new Node(w, dis[w]));
                    pre[w] = v;
                }
            }
        }
    }

    public int[] result() {
        return dis;
    }

    // 获得源到节点 t 的具体路径
    public Iterable<Integer> path(int t) {
        ArrayList<Integer> path = new ArrayList<>();
        if (!visited[t]) {
            return path;
        }
        int cur = t;
        while (cur != s) {
            path.add(cur);
            cur = pre[cur];
        }
        path.add(s);

        Collections.reverse(path);
        return path;
    }
}

Bellman-Ford 算法

Bellman-Ford 算法也是求解单源最短路径的算法，与 Dijkstra 算法不同的是，它能够处理负权边，即使允许图中存在权值为负数的边。

在讲解 Bellman-Ford 算法之前，我们来看一组操作

dis[w] = Math.min(dis[w], dis[v] + graph.getWeight(v, w));

这个操作叫做松弛操作。

为什么叫松弛，因为本来可以直接到达点 w，现在经过上面的操作之后，偏要经过点 v 然后到达 w (不一定会经过，只有当 dis[v] + graph.getWeight(v, w) < dis[w] 才会经过点 v)，如果把边看做橡皮筋的话，不就相当于松弛了吗?

而 Bellman-Ford 算法就是，对所有的边进行 $V - 1$ 轮松弛操作，这个 $V$ 指的是图中的节点数目，经过 $V - 1$ 轮松弛操作后，此时 dis 数组中保存的就是源点到各个节点的最短路径。

为了理解 Bellman-Ford 算法为什么这么神奇，每个节点经过 $V-1$ 轮松弛操作之后就可以得到最短路径，我们还是要研究一下松弛操作

dis[w] = Math.min(dis[w], dis[v] + graph.getWeight(v, w));

如果进行了松弛操作，意味源多经过了一条边到 w，所以如果我们设定 dis[w] 为源点最多经过 $k$ 条边到达点 w 的最短路径，那么经过一次松弛操作之后 dis[w] 语义变为源点最多经过 $k + 1$ 条边到达点 w 的最短路径，因为一个节点到达另一个节点最多经过 $V-1$ 条边，因此经过 $V - 1$ 轮的松弛操作之后，dis[w] 语义变为了源点最多经过 $V - 1$ 条边到达点 w 的最短路径，考虑到了源点到达节点 w 能经过的边数的所有情况，所以最终的 dis[w] 就是源点到点 w 的最短路径。

我们来看一个例子，假设源点为 0

图中有 4 个节点，因此要进行 3 轮松弛操作。第一次对所有边进行松弛操作

第二次对所有边进行松弛操作

第三次对所有边进行松弛操作

最后得到的结果为

	0	1	2	3
dis	0	4	1	2

Bellman-Ford 虽然能够处理负权边，但是如果图中有负权环的话，那么就无法求解了，所谓的负权环是指环中所以边的路径和为负值，这样的只要我每次经过一次环，每个节点的 dis 值都在减少，如果图中存在负权环的话，那么根本就不存在最小路径。

大家在考虑一个问题，对于无向图来说，如果图中出现了负权边意味着什么? 假设 0-1 是一个负权边，因为是无向图，可以从 0 到 1，也可以从 1-0，那么我们可以从 0 来到 1，然后从 1 来到 0，这就形成一个负权环。所以 Bellman-Ford 算法其实是一个有向图算法。

另外我们可以通 Bellman-Ford 算法检测图中是否存在负权环，我们知道如果如果不存在负权环的话，经过 $V-1$ 次松弛操作后，dis 数组中的元素的值是不会再改变的，所以我们可以经过 $V-1$ 次松弛操作后再次进行一次松弛操作，如果在这次的松弛操作中，dis 中有元素的值发生改变，那么就说明存在负权环。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class BellmanFord {
    private int[] dis;
    private WeightedGraph graph;
    private int s;
    private boolean hasNegativeCycle = false;
    private int[] pre;

    public BellmanFord(WeightedGraph graph, int s) {
        this.graph = graph;
        graph.validateVertex(s);
        this.s = s;
        this.dis = new int[graph.V()];
        this.pre = new int[graph.V()];

        Arrays.fill(dis, Integer.MAX_VALUE);
        Arrays.fill(pre, -1);
        dis[s] = 0;
        pre[s] = s;

        // k 代表轮数
        for (int k = 1; k < graph.V(); k++) {
            // 对所有边进行松弛操作，v-w 与 w-v 是两条边
            for (int v = 0; v < graph.V(); v++) {
                for (int w: graph.adj(v)) {
                    if (dis[v] != Integer.MAX_VALUE
                            && dis[v] + graph.getWeight(v, w) < dis[w]) {
                        dis[w] = dis[v] + graph.getWeight(v, w);
                        pre[w] = v;
                    }
                }
            }
        }

        // 再次进行一次松弛操作，检测负权环
        for (int v = 0; v < graph.V(); v++) {
            for (int w: graph.adj(v)) {
                if (dis[v] != Integer.MAX_VALUE
                        && (dis[v] + graph.getWeight(v, w) < dis[w])) {
                    hasNegativeCycle = true;
                }
            }
        }
    }

    public int[] result() {
        return dis;
    }

    public Iterable<Integer> path(int t) {
        ArrayList<Integer> path = new ArrayList<>();
        int cur = t;
        while (cur != s) {
            path.add(cur);
            cur = pre[cur];
        }
        path.add(s);

        Collections.reverse(path);
        return path;
    }
    
    public boolean isHasNegativeCycle() {
        return hasNegativeCycle;
    }
}

Floyed 算法

上面的两个算法解决的都是单源最短路径问题，而 Floyed 算法解决的所有点对之间的最短问题。我们其实可以通过使用 $V$ 次 Dijkstra 算法就可以求解所有点对之间的最短路径，不过 Dijkstra 算法不能处理负权边的问题，而 Floyed 算法可以处理负权边的问题。

但是同 Bellman-Ford 算法一样，如果图中存在负权环的话，就根本不存在最短路径，而我们知道如果无向图中有负权边的话，就相当于存在负权环，所以 Floyed 算法其实也是一个有向图算法。

Floyed 算法的思想也很简单，对于 v-w，假设它们之间的最短路径表示为 dis[v][w]，每一次都要尝试一下绕道点 t 会不会得到更短的路径(t 从节点 $0$ 取值到节点 $V-1$)，相当于

for(int t = 0; t < V; t++) {
    dis[v][w] = Math.min(dis[v][t] + dis[t][w], dis[v][w])
}

当经历过 $V$ 次的绕道尝试后，最终 dis[v][w] 就表示节点 v 与节点 w 之间的最短路径。

另外我们也可以通过 Floyed 算法对负权环进行检测，我们知道如果没有负权环的话 dis[v][v] 的值始终是 0，如果存在负权环的话，那么 dis[v][v] 的值就会更新为小于 0 的值，在经过 $V$ 次绕道之后检查所有的 dis[v][v] 是否等于 0 即可知道图中是否有负权环。

import java.util.Arrays;

public class Floyed {
    private WeightedGraph graph;
    private int[][] dis;
    private boolean hasNegativeCycle = false;

    public Floyed(WeightedGraph graph) {
        this.graph = graph;
        this.dis = new int[graph.V()][graph.V()];

        for (int i = 0; i < dis.length; i++) {
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }

        // 初始化 dis[][]
        for (int v = 0; v < graph.V(); v++) {
            dis[v][v] = 0;
            for (int w: graph.adj(v)) {
                dis[v][w] = graph.getWeight(v, w);
            }
        }

        // 绕道尝试
        for (int t = 0; t < graph.V(); t++) {
            for(int v = 0; v < graph.V(); v++) {
                for (int w = 0; w < graph.V(); w++) {
                    if (!(dis[v][t] == Integer.MAX_VALUE || dis[t][w] == Integer.MAX_VALUE)) {
                        dis[v][w] = Math.min(dis[v][w], dis[v][t] + dis[t][w]);
                    }

                }
            }
        }
        
        // 检测负权环
        for (int v = 0; v < graph.V(); v++) {
            if (dis[v][v] < 0) {
                hasNegativeCycle = true;
            }
        }
    }
    
    public int dis(int v, int w) {
        return dis[v][w];
    }
    
    public boolean isHasNegativeCycle() {
        return hasNegativeCycle;
    }
}