寒假，皮皮准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，皮皮希望在出发之前知道任意两个城市之前的最短路程。 1033450-20180623095244077-353646184.png 上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。 现在需要一个数据结构来存储图的信息，我们仍然可以用一个4*4的矩阵（二维数组e）来存储。比如1号城市到2号城市的路程为2，则设e[1][2]的值为2。2号城市无法到达4号城市，则设置e[2][4]的值为∞。另外此处约定一个城市自己是到自己的也是0，例如e[1][1]为0，具体如下。 1033450-20180623095252434-1650383278.png 基本要求 现在回到问题：如何求任意两点之间最短路径呢？通过之前的学习我们知道通过深度或广度优先搜索可以求出两点之间的最短路径。所以进行n2遍深度或广度优先搜索，即对每两个点都进行一次深度或广度优先搜索，便可以求得任意两点之间的最短路径。可是还有别的方法：Floyd-Warshall算法、Dijkstra算法等。请分别使用这两种算法求取任意两个城市到达的最短路径。允许通过所有顶点作为中转。

F-Warshall算法和Dijkstra算法都可以用来求解任意两个点之间的最短路径，但它们的时间复杂度和适用场景有所不同。

Floyd-Warshall算法适用于求解带权有向图中任意两个点之间的最短路径，时间复杂度为 $O(n^3)$。其基本思路是：设 $d_{i,j}$ 表示从节点 $i$ 到节点 $j$ 的最短路径长度，初始时 $d_{i,j}$ 被赋值为 $i$ 到 $j$ 的边的长度，若 $i$ 不能到达 $j$，则 $d_{i,j}$ 被赋值为正无穷大。然后，对于每一对节点 $i,j,k$，如果从 $i$ 到 $k$ 再到 $j$ 的路径比从 $i$ 直接到 $j$ 的路径更短，那么就更新 $d_{i,j}$，即 $d_{i,j}=\min(d_{i,j},d_{i,k}+d_{k,j})$。最终，$d_{i,j}$ 就表示从节点 $i$ 到节点 $j$ 的最短路径长度。

以下是使用Floyd-Warshall算法求解任意两个城市之间最短路径的Java代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        final int INF = Integer.MAX_VALUE;
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 城市数量
        int[][] e = new int[n+1][n+1]; // 存储图的信息
        // 读入图的信息
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    e[i][j] = 0; // 自己到自己的距离为0
                } else {
                    e[i][j] = INF; // 初始距离为无穷大
                }
            }
        }
        int m = in.nextInt(); // 公路数量
        for (int i = 1; i <= m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int w = in.nextInt();
            e[u][v] = w; // u到v的距离为w
        }
        // Floyd-Warshall算法求解任意两点之间最短路径
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    e[i][j] = Math.min(e[i][j], e[i][k] + e[k][j]);
                }
            }
        }
        // 输出任意两个城市之间的最短路径
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (e[i][j] == INF) {
                    System.out.print("∞ ");
                } else {
                    System.out.print(e[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

另一种算法是Dijkstra算法，它适用于求解有向图中一个起点到其它所有点的最短路径，时间复杂度为 $O(n^2)$。其基本思路是：设 $d_i$ 表示从起点到节点 $i$ 的最短路径长度，初始时 $d_i$ 被赋值为起点到 $i$ 的边的长度，若起点不能到达 $i$，则 $d_i$ 被赋值为正无穷大。然后，找到当前距离起点最近的节点 $j$，更新所有以 $j$ 为起点的边的终点 $k$ 的距离，即 $d_k=\min(d_k,d_j+w_{j,k})$。然后，找到当前距离起点最近的未访问节点 $j$，继续更新距离，直到所有节点都已访问完毕或当前没有可更新的节点为止。

以下是使用Dijkstra算法求解任意两个城市之间最短路径的Java代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        final int INF = Integer.MAX_VALUE;
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 城市数量
        int[][] e = new int[n+1][n+1]; // 存储图的信息
        // 读入图的信息
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    e[i][j] = 0; // 自己到自己的距离为0
                } else {
                    e[i][j] = INF; // 初始距离为无穷大
                }
            }
        }
        int m = in.nextInt(); // 公路数量
        for (int i = 1; i <= m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int w = in.nextInt();
            e[u][v] = w; // u到v的距离为w
        }
        // Dijkstra算法求解任意两点之间最短路径
        int[] d = new int[n+1]; // 存储起点到各个节点的最短路径
        boolean[] vis = new boolean[n+1]; // 标记节点是否已经访问过
        Arrays.fill(d, INF);
        d[1] = 0; // 起点为1号城市
        for (int i = 1; i <= n; i++) {
            int u = 0;
            // 找到当前距离起点最近的未访问节点
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (u == 0 || d[j] < d[u])) {
                    u = j;
                }
            }
            // 更新所有以 u 为起点的边的终点 k 的距离
            for (int k = 1; k <= n; k++) {
                if (e[u][k] != INF) {
                    d[k] = Math.min(d[k], d[u] + e[u][k]);
                }
            }
            vis[u] = true;
        }
        // 输出任意两个城市之间的最短路径
        for (int i = 1; i <= n; i++) {
            if (d[i] == INF) {
                System.out.print("∞ ");
            } else {
                System.out.print(d[i] + " ");
            }
        }
        System.out.println();
    }
}