带权值的最短路径

图示

如上的图示可由一组数据表示

• 0 1 12 -1 -1
• -1 0 9 3 -1
• -1 -1 0 -1 5
• -1 -1 4 0 13
• -1 -1 -1 -1 0

第n行第m个代表Vn到Vm的距离权值，不直接可达是-1，直接可达是对应权值,自己到自己的距离是0

注意：路径是单项的，Vn到Vm 和 Vm到Vn 权值很可能不同，比如一个是-1，一个是3

思路

深度优先遍历，在每一级探索出全部的可能，在一级中探索出所有可能的情况后，先选择一个深入，在下一级中再探索出所有可能，再选择一个深入，直到终结。次一级的所有情况已经完毕，然后回溯到上一级选择另一个可能去深入。每一级的所有情况都已经完毕的时候，就可以汇总出结果，得到局部解，可以反馈给上一级然后去汇总，最终得到最高一级中的结果即为所求。

代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int[][] weight = new int[6][];
        Scanner input = new Scanner(System.in);
        for (int i = 1; i < 6; i++) {
            String[] valuesStr = input.nextLine().split(" ");
            int[] values = new int[6];
            for (int j = 1; j < 6; j++) {
                values[j] = Integer.parseInt(valuesStr[j-1]);
            }
            weight[i] = values;
        }
        input.close();
        method(weight);
    }

    private static void method(int[][] weight) {
        for(int i = 2;i<6;i++){
            System.out.println(MinRoadLen(weight,1,i));
        }
    }

    private static int MinRoadLen(int[][] weight, int i,int j) {
        if(i==j) return 0;
        int min = Integer.MAX_VALUE;
        for(int k = 1;k<6;k++){
            if(k==i){
                continue;
            }else{
                if(weight[i][k]!=-1){
                    int reg = MinRoadLen(weight,k,j);
                    if(reg != 9999){
                        int res = weight[i][k] + reg;
                        if(res < min){
                            min = res;
                        }
                    }
                }
            }
        }
        if(min == Integer.MAX_VALUE){
            return 9999;
        }
        return min;
    }
}