经典最短路径算法学习笔记

前言

最短路径的概念

在一个图中，从一个顶点 到另一个顶点 存在着几条路径。路径是一个顶点到另一个顶点所经过的边的集合。路径的长度为所经过的边的权值之和。

• 在不带权图中（图中的边没有值），默认一个边值为1，即每条边的带权值为1，这样可以算出每条路径的长度，取其中的长度值最小的为这两个点的最短路径。
• 在带权图中，同样，计算出每条路径的长度，取其中最短的为两点间的最短路径。

note：一般的，如果两个点之间没有路径，即不可达，则这两个点的最短路径的长度可以设为无穷大。

单源最短路径的概念

单源最短路径，就是只有一个源点，求该源点到其他各点的最短路径。通俗的说，就是求出从一个顶点到其余顶点的最短路径。

解决该类问题的经典算法就是Dijkstra算法。想了解Dijkstra这个计算机科学家的可自行百度、谷歌~

Dijkstra算法的限制：该算法只能解决各边权值大于0的最短路径。

多源最短路径的概念

多源最短路径，对照单源最短路径，显而易见的，这边的源点是多个，求每个源点到其他各点的最短路径。通俗的说，就是求每对顶点之间的最短路径。

显然的，Dijkstra算法也可以用来解决该问题，只不过需要在求解完一个源点后，再让其他的点来当源点再次求解，重复执行，最终也可以得到所有的解。

除此之外，Floyd算法也可以用来解决该问题。

单源最短路径——Dijkstra算法

首先，从大的方面上讲，Dijkstra算法用到的思想是贪心思想。其中，贪心选择方法为每一步，选择离当前点最近的点作为最短路径中经过的点。（这个选择方法是我自己总结的，emm可能说的不怎么样，但我尽力了QAQ）

Dikjstra算法的流程：

1. 首先，定义一个数组dist来保存源点s到其他点的距离，定义一个集合visited记录访问过的节点，在这个visited集合中任意一点x都是已经求得从s到x的最短路径。一开始，visited中只有源点s；dist中的初始值为以下两种选择：
   • 如果s可以到v点，那么$dist[v] = length[s,v] $（边sv的权值）
   • 否则，那么\(dist[v] = \infty\)；
2. 每一次确定了一个点v的最短路径，就把v放入visited集合中，然后对于未访问过的任意节点x，选出其中dist[x]最小的点，这个点dist[x]为源点s到x的最短路径的长度。然后以此x为中间点，更新dist数组。更新操作为：
   • 对于节点u，\(dist[u] = Min(dist[u], dist[x]+length[x,u])\)；
3. 循环执行第二步，直到visited中包含图中所有的点。

算法正确性证明：

友情提示：这个证明是我在看了维基百科和数据结构书再加上自己的思考后整理出来的，准确性不敢保证 O.O

在证明这个正确性之前，先证明下面这个。

命题如下：

若从源点v到某个顶点j的最短路径是\((v,...,a,...u,j)\)，也就是说，在源点v->j的最短路径上顶点j的前一个顶点是u，那么其中的\((v,...,a,...u)\)一定是源点v->u的最短路径。

求证：

反证法证明。

假设\((v,...,a,...,u,j)\)是源点v到顶点j的最短路径，但\(（v,...,a,...,u）\)不是源点v->u最短路径。由于\((v,...,a,...,u)\)不是源点v->u的最短路径，设源点v->u的最短路径为\(（v,...,b,...,u）\)，如下图所示，则\((v,...,b,...,u,j)\)是一条比\(（v,...,a,...,u,j）\)更短的新路径，与前面的假设矛盾，命题得证。

证明展示图

现在证明Dijkstra算法正确性。

假设：任意一个已访问过的点v，若在未访问的点中，dist[u]的值最小。并且，在形成dist[u]长度的路径上u的前一个点为v。所以，\(dist[u] = dist[v]+length[v,u]\)；

按照Dijkstra算法，此时源点s到u的最短路径已经确定，且值为dist[u]；

依旧采用反正法证明：

若现在存在一条更短的路径到u，且u的前一个点为w。

w有两种情况：

1. 该点为未访问节点，所以\(dist[w] > dist[u]\)；
2. 该点为已访问节点。

对于第一种情况：

第一种证明图

对于第二种情况：

第二种证明图

故，通过反证法证明得Dijkstra算法正确。

note:

1. Dijkstra算法，若现在已选v点，下一个点不是选距离v最近的点u，而是选dist[u]最小的点u。
2. 在维基百科上看到，Dijkstra算法的原始版本是找出两点之间的最短路径。

贴个代码：

/**
 * Dijkstra算法
 * 例子为有向图
 * 输入
 * n 表示顶点的个数，顶点的编号从0开始
 * edges[m][i,j,w] m为第几条边， i,j为一条边的两个节点，且 i->j,w为这条边的权重(w >= 0)
 * root 表示源点
 *
 * 输出
 * 输出一个一维数组dist,表示root到其他各点最短路径长度
 */
public class Dijkstra {
    private int[] dist;
    private int[] path;

    public int[] shortestPath(int n,int[][]edges,int root ) {
        dist = new int[n]; // 保存最短路径长度
        path = new int[n]; // 保存最短路径
        boolean[] visit = new boolean[n]; // 记录节点是否访问过，访问过代表此点已确定了最短路径
        int[][] adj = new int[n][n]; // 邻接矩阵
        // 初始化邻接矩阵，默认两点之间不相连，值为无穷大，在这里用Integer.MAX_VALUE表示
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                adj[i][j] = Integer.MAX_VALUE;
            }
        }
        // 赋值邻接矩阵
        for (int i = 0; i < edges.length; i++) {
            adj[edges[i][0]][edges[i][1]] = edges[i][2];
        }
        // 初始化dist和path
        for (int i = 0; i < n; i++) {
            dist[i] = adj[root][i];
            if (dist[i] != Integer.MAX_VALUE) {
                path[i] = root;
            }
            else path[i] = -1;
        }
        // 将源点标为已访问
        visit[root] = true;
        dist[root] = 0;
        path[root] = root;

        int flag = n-1,curNode = 0,minValue;

        while (flag != 0) {
            // 找出当前dist中路径长度最短的那个点作为下一个点
            minValue = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (visit[i]) continue;
                if (minValue > dist[i]) {
                    minValue = dist[i];
                    curNode = i;
                }
            }
            // 标记找出来的点
            visit[curNode] = true;
            flag--;

            // 通过curNode，更新dist和path
            for (int i = 0; i < n; i++) {
                if (visit[i] || adj[curNode][i] == Integer.MAX_VALUE) continue;
                if (dist[i] > dist[curNode]+adj[curNode][i]) {
                    dist[i] = dist[curNode]+adj[curNode][i];
                    path[i] = curNode;
                }
            }
        }
        return dist;
    }

    /**
     * 递归打印路径
     * @param root 源点
     * @param end 终点
     */
    public void dfs(int root, int end) {
        if (end != root) {
            dfs(root,path[end]);
        }
        System.out.print(end+" ");
    }

    public static void main(String[] args) {
        Dijkstra h = new Dijkstra();

        // 测试
        int n = 7;
        int[][] edges = {{0,1,4},{0,2,6},{0,3,6},{1,2,1},{1,4,7},{2,4,6},{2,5,4},{3,2,2},{3,5,5},{4,6,6},{5,4,1},{5,6,8}};
        int root = 0;

        int[] dist = h.shortestPath(n,edges,0);

        for (int i : dist) {
            System.out.print(i+" ");
        }
        System.out.println();
        for (int i = 0; i < n; i++) {
            System.out.print(root+"->"+i+": ");
            h.dfs(root,i);
            System.out.println();
        }
    }
}

测试的结果：

0 4 5 6 10 9 16 
0->0: 0 
0->1: 0 1 
0->2: 0 1 2 
0->3: 0 3 
0->4: 0 1 2 5 4 
0->5: 0 1 2 5 
0->6: 0 1 2 5 4 6

多源最短路径——Floyd算法

Floyd算法的流程

1. 假定图graph的顶点的索引编号从1到N，二维数组dp用来保存答案，dp[i][j]表示顶点i到顶点j的最短路径长度。初始时，dp[i][j]的值为：
   • i与j相连，\(dp[i][j] = length[i,j]\);(边ij的权值)
   • i与j不相连，\(dp[i][j] = \infty\);
2. 对于\(\forall k \in (1,N),\forall i \in (1,N), \forall j \in (1,N)\), 进行\(dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])\)迭代。
3. 三层循环后，返回dp数组即为所有点之间的最短路径。

算法的理解

通过上述的流程可以看出，Floyd算法的思想是动态规划。

定义：\(f(i,j,k)\)为顶点i只能经过\((1,2,...,k)\)这些作为中间点的情况下，到顶点j的最短路径。

也就说，当\(k = N\)时，\(f(i,j,N)\)后的\(dp[i][j]\)就为\(i \to j\)的最短路径长度。

递推式推导

对于每一对顶点，\(f(i,j,k)\)可能会产生的情况：

• \(i \to j\) 不会经过k，那么 \(f(i,j,k) = f(i,j,k-1)\)；因为不会经过k，所以跟之前的k-1是一样的，此时，这里的\(f(i,j,k-1)\)是前一个状态，也就是说只要保存前一个状态下的所有对顶点的最短路径即可。
• $i j $ 会经过k，那么\(f(i,j,k) = f(i,k,k-1)+f(k,j,k-1)\)；因为会经过k，那就说明\(i \to k \to j\)是可以的，所以\(f(i,j,k)\)可以表示成\(f(i,k,k-1)+f(k,j,k-1)\)。在这里的\(f(i,k,k-1)\)和\(f(k,j,k-1)\)也是前一个状态。

综上，\(f(i,j,k) = min(f(i,j,k-1),f(i,k,k-1)+f(k,j,k-1))\)；

理解

若定义二维数组dp来保存所有对顶点的最短路径的长度，那么在上述的推导下，迭代公式即为：

\(dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])\)

其中，在等式的右边\(dp[i][j],dp[i][k],dp[k][j]\)都为前一个状态下的产物。

贴个代码：

/**
 * floyd算法
 * 举的例子和Dijkstra算法是一致的
 */
public class Floyd {

    /**
     * floyd 最短路径
     * @param n 顶点数
     * @param edges 边 
     * @return 二维数组 表示每对顶点的最短路径
     */
    public int[][] shortestPath(int n,int[][] edges) {
        int[][] dp = new int[n][n]; 
        // 初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) dp[i][j] = 0;
                else dp[i][j] = Integer.MAX_VALUE;
            }
        }
        // 赋值
        for (int i = 0; i < edges.length; i++) {
            dp[edges[i][0]][edges[i][1]] = edges[i][2];
        }

        // 三重循环
        int k = 0;
        for (;k < n;k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j || dp[i][k] == Integer.MAX_VALUE || dp[k][j] == Integer.MAX_VALUE) continue;
                    dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k][j]);
                }
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        Floyd h = new Floyd();
        
        // 测试
        int n = 7;
        int[][] edges = {{0,1,4},{0,2,6},{0,3,6},{1,2,1},{1,4,7},{2,4,6},{2,5,4},{3,2,2},{3,5,5},{4,6,6},{5,4,1},{5,6,8}};

        int[][] ans = h.shortestPath(n,edges);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (ans[i][j] == Integer.MAX_VALUE)
                    System.out.print("∞ ");
                else System.out.print(ans[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

测试的结果：

0 4 5 6 10 9 16 
∞ 0 1 ∞ 6 5 12 
∞ ∞ 0 ∞ 5 4 11 
∞ ∞ 2 0 6 5 12 
∞ ∞ ∞ ∞ 0 ∞ 6 
∞ ∞ ∞ ∞ 1 0 7 
∞ ∞ ∞ ∞ ∞ ∞ 0 

参考文献

• https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
• https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

如有不正确的地方，欢迎指正( •̀ ω •́ )✧