题意解析

Dijkstra算法逻辑：以源点为中心，逐步遍历离源点最近的节点（权重和最小），并更新该节点出度对应节点的离源点最小值。
1.维护一个st数组，用于保存所有出度已经计算完成的节点;dist数组用于保存节点距离源点的最小距离（边的权重和最小），dist[0]=0,表示源点自身距离，dist其他值为+∞，表示还未计算的节点到源点距离；adj为邻接矩阵，用于保存各节点的度及权；
2.依次遍历各节点，从adj邻接矩阵中选出”距离最短的顶点（出度权重最小的节点）t”，并将顶点t置为已计算（st[t]=true）；同时，更新t节点出度对应节点的离源点最小值。

Dijkstra算法Java版

朴素版Dijkstra算法

由题可知，该图为m>=n^2的绸密图，所以采用邻接矩阵存储

$O(n^2)$

Java 代码

class Main{
    //邻接矩阵
    private static int[][] adj;
    //最短路径
    private static int[] dist;
    //是否已确定最短路径
    private static boolean[] st;
    private static int n;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] a=br.readLine().split(" ");
        n=Integer.parseInt(a[0]);
        int m=Integer.parseInt(a[1]);
        adj=new int[n][n];
        dist=new int[n];
        st=new boolean[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                adj[i][j] = Integer.MAX_VALUE;
            }
        }
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[0]=0;
        //创建邻接矩阵
        while(m-- >0){
            String[] t=br.readLine().split(" ");
            int i=Integer.parseInt(t[0])-1,j=Integer.parseInt(t[1])-1,w=Integer.parseInt(t[2]);
            if(i==j){
                //防止自环出现
                adj[i][j]=0;
            }else{
                //去除重边
                adj[i][j]=Math.min(adj[i][j],w);
            }
        }
        System.out.print(dijkstra());
    }
    private static int dijkstra(){
        //最后汇点到汇点的权重一定为0，所以当计算到倒数第二个节点后，所有距离源点的最小距离已经计算完成，无需再遍历一次
        for(int i=0;i<n-1;i++){
            int t=-1;
            //遍历节点所有出度，找出最小权
            for(int j=0;j<n;j++){
                if(!st[j]&&(t<0||dist[t]>dist[j])){
                    t=j;
                }
            }
            st[t]=true;
            for(int k=0;k<n;k++){
                //adj[t][k]初始化为MAX_VALUE，加上防止溢出
                if(adj[t][k]!=Integer.MAX_VALUE){
                    dist[k]=Math.min(dist[k],dist[t]+adj[t][k]);
                }
            }
        }
        if(dist[n-1]==Integer.MAX_VALUE){
            return -1;
        }
        return dist[n-1];
    }
}