5-Dijkstra算法

算法思想

算法模板

朴素算法

import java.util.*;
public class Main {
    static int N = 510, M = 0x3f3f3f3f;;
    // dist[i]存储（1号点到）i 号点的最短距离
    static int[] dist = new int[N];
    // g[][]存储每条边的长度
    static int[][] g = new int[N][N];
    // st[i]标记（1号点到）i 号点的最短距离是否已经确定
    static boolean[] st = new boolean[N];
    static int n, m;


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 1; i <= n; i ++ ) Arrays.fill(g[i], M);
        Arrays.fill(dist, M);
        
        while(m -- > 0)
        {
            int from = in.nextInt(), to = in.nextInt();
            int weight = in.nextInt();
            
            g[from][to] = Math.min(weight, g[from][to]);
        }
        
        System.out.println(dijkstra());
    }
    

    public static int dijkstra()
    {
		Arrays.fill(dist, M);
        dist[1] = 0;

        for(int i = 0; i < n; i ++ )
        {
            int t = -1;
            // 在未确定最短路径的点中，选择一个距离（1号点）最近的点
            // 首次选择的是1号点自身
            for(int j = 1; j <= n; j ++ )
            {
                if(!st[j] && (t == -1 || dist[j] < dist[t]))
                    t = j;
            }
            
            for(int j = 1; j <= n; j ++)
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            
            st[t] = true;
        }
        
        return (dist[n] == M) ? -1 : dist[n];
    }
}

堆优化算法

import java.util.*;

public class Main {
    static int N = 150010, M = 0x3f3f3f3f;
    // 稀疏图使用邻接表
    static int[] e = new int[N],
        ne = new int[N],
        h = new int[N],
        w = new int[N];
    static int[] dist = new int[N];        
    static boolean[] st = new boolean[N];
    static PriorityQueue<Dist> q = new PriorityQueue<Dist>(Comparator.comparing(d -> d.length));
    // idx 代表点的索引（在数组 e, ne, h 当中），
    // 也代表边的索引（在数组 w 当中）
    static int n, m, idx;
    
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        Arrays.fill(dist, M);
        Arrays.fill(h, -1);
        
        while(m -- > 0)
        {
            int from = in.nextInt(), to = in.nextInt();
            int weight = in.nextInt();
            add(from, to, weight);
        }
        
        System.out.println(dijkstra());
    }
    
    static void add(int u, int x, int weight)
    {
        e[idx] = x;
        w[idx] = weight;
        ne[idx] = h[u];
        h[u] = idx ++;
    }
    
    static int dijkstra()
    {
        dist[1] = 0;
        q.offer(new Dist(1, 0));
        
        while(!q.isEmpty())
        {
            Dist t = q.poll();
            int end = t.end, length = t.length;
            
            if(st[end]) continue;
            st[end] = true;
            
            int p = -1;
            for(int i = h[end]; i != -1; i = ne[i])
            {
                int k = e[i];
                int weight = w[i];
                if(st[k]) continue;
	            // 当最短路径可以缩短时
                if(dist[end] + weight < dist[k])
                {
                    dist[k] = dist[end] + weight;
                    q.offer(new Dist(k, dist[k]));
                }
            }
        }
        
        return dist[n] == M ? -1 : dist[n];
    }
}


class Dist 
{
    // end 代表 end 号点
    // length 代表（局部情况下的）1号点到 end 号点的最短距离
    int end, length;
    public Dist(int end, int length)
    {
        this.end = end;
        this.length = length;
    }
}