dijkstra算法的两种解法以及Bellman_ford算法的两种算法，共四种算法都是单源最短路。

本体要求多源最短路，即求对多个起点到对各终点的多条最短路径。

Floyd算法可以解决正负权值的无向图问题。

核心思想是动态规划

节点1到节点5的最短距离dp[1][5] 可以 由 节点1到节点3的最短距离dp[1][3]加上节点3到节点5的最短距离dp[3][5]得到，即dp[1][5] = dp[1][3] + d[3][5];

又或者 可以由 节点1到节点2的最短距离dp[1][2]加上节点2到节点5的最短距离dp[2][5]得到，即dp[1][5] = dp[1][2] + d[2][5];

以及其它所有的可能得到的路径走法，以此类推，我们需要找到这些路径走法中的最优方案。

搬出递归五部曲

1、确定dp数组以及下标含义

2、确定递推公式

3、dp数组如何初始化、

4、确定遍历顺序

5、打印dp数组

先看第一步：确定dp数组以及下标含义

dp[i][j][k] = m 表示起点为i，终点为j，中间可能经过k（k的取值范围为从1到k）个节点最短路径距离为m

第二步：确定递推公式

两种情况：

（1）节点i到节点j的最短路径经过节点k，即dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1];

（2）节点i到节点j的最短路径不经过节点，即dp[i][j][k] = dp[i][j][k-1];

所以dp[i][j][k] = Math.min(dp[i][k][k-1] + dp[k][j][k-1], dp[i][j][k-1]);

第三步：dp数组初始化

先来看k如何取值

递推公式可知我们是从k-1的状态来推出k的状态，所以初始化的时候将k赋值为0。在下一轮计算的时候，就可以根据 dp[i][j][0] 来计算 dp[i][j][1]，此时的 dp[i][j][1] 就是 节点i 经过节点1 到达 节点j 的最小距离了

再来看dp值怎么取值

同时还要注意，将i==j的dp元素赋值为0，因为起点i和终点j是同一个节点的时候，最短距离一定是0。

除此之外，其他的dp[i][j][0]都初始化为最大值即可。

for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 0; k <= n; k++){
                    if(i == j ){
                        dp[i][j][k] = dp[j][i][k] = 0;                    
            }
                    dp[i][j][k] = dp[j][i][k] = 10005;
                }
    }
}

第四步：遍历顺序

因为k依赖k-1，而i和j并不依赖自身状态

所以k的for循环一定在外面，而i和j的for循环谁前谁后无所谓。

完整代码如下：

import java.util.*;

public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][][] dp = new int[n + 1][n + 1][n + 1];
        //dp数组初始化最大值
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 0; k <= n; k++){
                    if(i == j ){
                        dp[i][j][k] = dp[j][i][k] = 0;                    }
                    dp[i][j][k] = 10005;
                    dp[j][i][k] = 10005;
                }
            }
        }
        //输入权值以及初始化
        for(int i = 0; i < m; i++){
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            dp[u][v][0] = w;
            dp[v][u][0] = w;
        }

        //确定遍历顺序
        for(int k = 1; k <= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    //递推公式
                    dp[i][j][k] = Math.min(dp[i][k][k-1] + dp[k][j][k-1], dp[i][j][k-1]);
                }
            }
        }
        
        int Q = scanner.nextInt();
        for(int i = 0; i < Q; i++){
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            if(dp[start][end][n] == 10005){
                System.out.println(-1);
            }else{
                System.out.println(dp[start][end][n]);
            }
        }
    }

}