题

package package1;

import java.util.Arrays;

/** * 保存内容的列表 */
class List {
   
    int[] weight;//权值
    int[] sortYes;//可排序的权值
    String[] str;//保存最后输出的路径

    public List(int n) {
   
        weight = new int[n];
        sortYes = new int[n];
        str = new String[n];
        for (int i = 0; i < n; i++) {
   
            weight[i] = Integer.MAX_VALUE;//初始值最大值，之后更新直接比较大小
            sortYes[i] = Integer.MAX_VALUE;//寻找最小值所保存的列表
        }
    }
}

public class alg {
   
    /** * dijkstra{ * 加入第一个 * * while 找最小{ * 去掉最小 * 加入其他,加上权值 * } * } */
    public static void dijkstra(int[][] g, List list, boolean direction) {
   
        list.sortYes[0] = 0;//从第一个开始找，只需要为第一个赋值0
        while(list.sortYes[min(list.sortYes)] != Integer.MAX_VALUE){
   //当最小值为MAX_VALUE的时候说明没有最小值了，已经结束
            int point = min(list.sortYes);
            list.sortYes[point] = Integer.MAX_VALUE;
            for(int i = 1; i < g[0].length; i++){
   //加入其他,加上权值
                if(g[point][i] != 0){
   //权值等于零直接跳过
                    if( point == 0){
   //第0个，直接加入
                        list.weight[i] = g[point][i];
                        list.sortYes[i] = g[point][i];
                        list.str[i] = (char)(point + 97) + " -> " + (char)(i + 97);//更新路径信息
                        if(!direction){
   //是无向图，让对称点=0
                            g[i][point] = 0;
                        }
                    }else{
   //不是 第0个
                        int weight = list.weight[point] + g[point][i];
                        if(weight < list.weight[i]){
   //把当前点的权值加上以当前点为起点的下一点的权值的和作为权值
                            list.weight[i] = weight;
                            list.sortYes[i] = g[point][i];
                            list.str[i] = list.str[point] + " -> " + (char)(97 + i);//更新路径信息
                            if(!direction){
   //是无向图，让对称点=0
                                g[i][point] = 0;
                            }
                        }
                    }
                }
            }
        }
    }

    /** * 求最小值的函数 * @param sortYes * @return */
    public static int min(int[] sortYes){
   
        int t = sortYes[0];
        int r = 0;
        for(int i = 1; i < sortYes.length; i++){
   
            if(sortYes[i] < t){
   
                t = sortYes[i];
                r = i;
            }
        }
        return r;
    }

    /** *初始化图 * @param g 图 * @param n 点 * @param direction 是否有向 */
    public static void initGraph(int[][] g, int[][] n, boolean direction) {
   
        for (int[] ints : n) {
   
            if (direction) {
   
                g[ints[0] - 1][ints[1] - 1] = ints[2];
            } else {
   
                g[ints[0] - 1][ints[1] - 1] = ints[2];
                g[ints[1] - 1][ints[0] - 1] = ints[2];
            }
        }
        for (int[] ints : g) {
   
            System.out.println(Arrays.toString(ints));
        }
    }

    public static void main(String[] args) {
   
        System.out.println("-----------------第一题------------------");
        int[][] n = {
   {
   1,4,7},{
   2,1,3},{
   2,3,4},{
   3,5,6},{
   4,2,2},{
   4,3,5},{
   5,4,4}};
        int[][] g = new int[5][5];
        initGraph(g, n, true);

        List list = new List(5);
        dijkstra(g, list, true);
        for(int i = 1; i < list.weight.length; i++){
   
            System.out.println(list.str[i] + " >" + list.weight[i] + "<");
        }

        System.out.println("-----------------第二题------------------");
        int[][] n1 = {
   {
   1,2,3},{
   1,4,4},{
   1,3,5},{
   2,5,3},{
   2,6,6},{
   4,3,2},{
   4,8,5},{
   4,5,1},{
   6,5,2},{
   6,10,5},{
   7,3,4},{
   7,8,3},{
   7,11,6},{
   9,8,6},{
   9,5,4},{
   9,10,3},{
   9,12,5},{
   11,12,8},{
   11,8,7},{
   12,10,9}};
        int[][] g1 = new int[12][12];
        initGraph(g1, n1, false);

        List list1 = new List(12);
        dijkstra(g1, list1, false);
        for(int i = 1; i < list1.weight.length; i++){
   
            System.out.println(list1.str[i] + " >" + list1.weight[i] + "<");
        }
    }
}

结果