题目描述

Dijkstra求最短路径1

JAVA代码

import java.util.*;
import java.io.*;

class Main{

    static int N = 510, n,m;
    static int[][] g = new int[N][N];//稠密图使用邻接矩阵
    static int[] d= new int[N];
    static boolean[] st = new boolean[N];//相当于s集合, 确定离1号的最短距离的集合
    static int max = 1<<30;

    static int dijkstra(){
        //初始化
        Arrays.fill(d, max);
        d[1] = 0;
        //循环n-1次,将除1节点外的n-1个点加入s集合中
        for(int i=0; i<n-1;i++){
            int t = -1;

            //确定当前最短节点到1号点的距离.
            for(int j = 1; j<=n; j++){
                if(st[j])continue;
                if(t==-1|| d[j]<d[t]){
                    t = j;//t记录当前点的位置.
                }
            }
            st[t] = true;
            //更新其他节点到当前节点的最短距离
            if (d[t] == max) return -1 ;
            for(int j = 1; j<=n; j++){
                if(d[j] > d[t] + g[t][j]) {
                   d[j] = d[t]+g[t][j];
                }
            }


        }
        if(d[n]==max) return -1; 
        else return d[n];

    }

    public static void main(String args[]){
        Scanner sc = new Scanner(new InputStreamReader(System.in));
        n = sc.nextInt();
        m = sc.nextInt();

        for(int i = 1; i<=n; i++){
            Arrays.fill(g[i], max);
        }

        while(m-->0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            g[a][b] = Math.min(g[a][b], c);
        }
        System.out.println(dijkstra());
    }
}