3、最短路径算法 & Dijkstra & Floyd

AcWing 849. Dijkstra求最短路 I

AcWing 850. Dijkstra求最短路 II

AcWing 854. Floyd求最短路

第一种：自己实现的，不断更换中转点的一个过程

//需要注意重复边，取较小的那个权值

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.Dijkstra();
    }

    int n, m;
    int[][] lines;
    int[] values;
    int used[];
    int EXCEED = 99999999;

    void Dijkstra() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        lines = new int[n + 1][n + 1];
        values = new int[n + 1];
        used = new int[n + 1];
        Arrays.fill(values, EXCEED);
        for (int i = 0; i < lines.length; i++) {
            Arrays.fill(lines[i], EXCEED);
        }

        Arrays.fill(used, -1);
        values[1] = 0;
        used[1] = 0;
        while (m-- > 0) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int z = scanner.nextInt();
            if (lines[x][y] < z) {
                z = lines[x][y];
            }
            lines[x][y] = z;
            if (x == 1) values[y] = z;
        }
        while (true) {
            int middle = EXCEED;
            int mid_pos = -1;
            for (int i = 1; i <= n; i++) {
                if (used[i] == -1 && values[i] < middle) {
                    middle = values[i];
                    mid_pos = i;
                }
            }
            if (mid_pos == -1) break;
            used[mid_pos] = 1;
            for (int i = 1; i <= n; i++) {
                if (values[mid_pos] + lines[mid_pos][i] < values[i]) {
                    values[i] = values[mid_pos] + lines[mid_pos][i];
                }
            }
        }
        if (values[n] == EXCEED) System.out.println("-1");
        else System.out.println(values[n]);
    }
}

迪杰斯特拉算法的堆优化

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.Dijkstra();
    }

    int n, m;
    int N=1000010;
    int[] dist;
    int[] used;
    int []h=new int[N];
    int []e=new int[N];
    int []ne=new int[N];
    int []w=new int[N];
    int idx=1;
    //构造小顶堆：
    PriorityQueue<VerC> small_heap=new PriorityQueue<>();
    //用的是优先队列
    int EXCEED = 99999999;
    class VerC implements Comparable{
        int id,dist;
        public VerC(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }

        @Override
        public int compareTo(Object o) {
            VerC verC= (VerC) o;
            return dist-verC.dist;
        }
    }
    void insert(int a,int b,int c){
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    void Dijkstra() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        dist = new int[n + 1];
        used = new int[n + 1];
        Arrays.fill(dist, EXCEED);
        Arrays.fill(used, -1);
        Arrays.fill(h, -1);
        dist[1] = 0;
        used[1] = 1;
        small_heap.offer(new VerC(1,0));
        while (m-- > 0) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int z = scanner.nextInt();
            insert(x,y,z);
        }
        while(!small_heap.isEmpty()){
            VerC verC=small_heap.poll();
            int mid_pos=verC.id;
            for(int i=h[mid_pos];i!=-1;i=ne[i]){
                int j=e[i];
                //j是头结点的下一个结点值
                //w[i]代表从头结点e[i]到j的距离
                if(dist[j]>dist[mid_pos]+w[i]&&used[j]==-1){
                    dist[j]=dist[mid_pos]+w[i];
                    small_heap.offer(new VerC(j,dist[j]));
                }
            }
            used[mid_pos]=1;
        }
        if(dist[n]== EXCEED) System.out.println(-1);
        else System.out.println(dist[n]);
    }
}

Floyd最短路径算法

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.Floyd();
    }

    int n, m;
    int[][] g;
    int[] values;
    int EXCEED = 10000010;
    int EXCEED_LINE = 100010;

    //一开始错的根本原因是
    //没有考虑重复边覆盖的特殊情况
    //每次给边定权值的时候应该考虑最小的那个情况
    void Floyd() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        int kk = scanner.nextInt();
        g = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(g[i], EXCEED);
            g[i][i] = 0;
        }
        while (m-- > 0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int z = scanner.nextInt();
            g[a][b] = Math.min(g[a][b],z);
        }
        //k是具体选用的哪个中转点
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    g[i][j] = Math.min(g[i][k] + g[k][j], g[i][j]);
        for (int i = 0; i < kk; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            if (g[x][y] >= EXCEED_LINE) {
                System.out.println("impossible");
            } else {
                System.out.println(g[x][y]);
            }
        }
    }
}