最短路算法

dijkstral

import java.util.*;

public class Main{
    static int N = 510;
    static int[] dist = new int[N];
    static int[][] g = new int[N][N];
    static boolean[] st = new boolean[N];
    static int n,m;
    
    public static int dijkstra(){
        Arrays.fill(dist,0x3f3f3f);
        dist[1] = 0;
        for(int i = 0; i < n; i ++){
            int t = -1;
            for(int j = 1; j <= n; j ++ ){
                if(!st[j] && (t == -1 || dist[t] > dist[j])){
                    t = j;
                }
            }
            st[t] = true;
            for(int j = 1; j <= n; j ++){
                dist[j] = Math.min(dist[j],g[t][j] + dist[t]);
            }
        }
        if(dist[n] == 0x3f3f3f)return -1;
        else return dist[n];
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int[] x : g)Arrays.fill(x,0x3f3f3f);
        while(m -- > 0){
            int a = sc.nextInt(),b = sc.nextInt(),c = sc.nextInt();
            g[a][b] = Math.min(g[a][b],c);
        }
        System.out.println(dijkstra());
    }
}

dijkstral(堆优化)

public static int dijkstral(int s){
        Arrays.fill(st,false);
        Arrays.fill(d,0x3f3f3f);
        d[s] = 0;
        PriorityQueue<PII> heap = new PriorityQueue<>((p1,p2) -> p1.x - p2.x);
        heap.add(new PII(0,s));

        while(heap.size() > 0){
            PII cur = heap.poll();
            int dis = cur.x, v = cur.y;
            if(st[v])continue;
            st[v] = true;

            for(int i = h[v];i != -1;i = ne[i]){
                int j = e[i];
                if(d[j] > dis + w[i]){
                    d[j] = dis + w[i];
                    heap.add(new PII(d[j],j));
                }
            }
        }
        ...
    }
class PII{
    int x;
    int y;
    public PII(int x,int y){
        this.x = x;
        this.y = y;
    }

Bellman-Ford

int bellman_ford()
{
    Arrays.fill(dist, 0x3f3f3f);
    dist[1] = 0;
    for (int i = 0; i < n; i ++ ){
        int[] backup = Arrays.copyOf(dist,n);//备份操作
        for (int j = 0; j < m; j ++ ){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            backup[b] = Math.min(backup[b],d[a] + w);
        }
    	 d = backup;
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}
class Edge{
    int a;
    int b;
    int w;
}

spfa

public static int spfa(){
        Arrays.fill(d,0x3f3f3f);
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        d[1] = 0;
        st[1] = true;
        while(q.size() > 0){
            Integer cur = q.poll();
            st[cur] = false;

            for(int i = h[cur];i != -1;i = ne[i]){
                int j = e[i];

                if(d[j] > d[cur] + w[i]){
                    d[j] = d[cur] + w[i];
                    if(!st[j]){
                        st[j] = true;
                        q.add(j);
                    }
                }
            }
        }
        if(d[n] == 0x3f3f3f)return Integer.MIN_VALUE;
        return d[n];
    }

floyd

	public static void floyd(){
        for(int k = 1;k <= n;k ++){
            for(int i = 1;i <= n;i ++){
                for(int j = 1;j <= n;j ++){
                    d[i][j] = Math.min(d[i][j],d[i][k]+d[k][j]);
                }
            }
        }
    }