最短路算法dijkstra算法

import java.util.*;
public class Main {
   
    static void dijstra(int[][] g, int[] dist, int n, int x) {
        boolean[] st = new boolean[n+1];
        dist[x] = 0;
        for(int i=1; i <= n; i++) {
            int t = -1;
            for(int j=1; j <= n; j++) 
                if(st[j] == false && (t == -1 || dist[t] > dist[j]))
                    t = j;
            st[t] = true;
            for(int j=1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }
        //System.out.println(Arrays.toString(dist));
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] g = new int[n+1][n+1];
        int[] dist = new int[n+1];
        for(int i=0; i <= n; i++) 
            for(int j=0; j <= n; j++) 
                if(i == j) g[i][i] = 0;
                else g[i][j] = Integer.MAX_VALUE >> 1;
        for(int i=0; i < m; i++){
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            g[x][y] = Math.min(g[x][y], z);
        }
        //System.out.println(Arrays.deepToString(g));
        Arrays.fill(dist, Integer.MAX_VALUE);
        dijstra(g, dist, n, 1);
        if(Integer.MAX_VALUE >> 1 == dist[n])
            System.out.println(-1);
        else
            System.out.println(dist[n]);
    }
}

不存在边初始化为-1的版本

import java.util.*;
public class Main {
   
    static void dijstra(int[][] g, int[] dist, int n, int x) {
        boolean[] st = new boolean[n+1];
        dist[x] = 0;
        for(int i=1; i <= n; i++) {
            int t = -1;
            for(int j=1; j <= n; j++) 
                if(st[j] == false && (t == -1 || dist[t] > dist[j]))
                    t = j;
            st[t] = true;
            for(int j=1; j <= n; j++) {
                if(g[t][j] != -1)
                    dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] g = new int[n+1][n+1];
        int[] dist = new int[n+1];
        for(int i=0; i <= n; i++) 
            for(int j=0; j <= n; j++) 
                if(i == j) g[i][i] = 0;
                else g[i][j] = -1;
        for(int i=0; i < m; i++){
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            if(x != y)
                g[x][y] = g[x][y] == -1 ? z : Math.min(g[x][y], z);
        }
        Arrays.fill(dist, Integer.MAX_VALUE);
        dijstra(g, dist, n, 1);
        if(dist[n] == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(dist[n]);
    }
}

最短路算法dijkstra算法

原文：https://www.cnblogs.com/lixyuan/p/13289409.html