最短路径

最短路径

这玩意尊嘟很基础，但是写得少，每次遇到都会愣住，干脆写一篇记录一下

Floyed

求出的是多源最短路，时间复杂度O(n^3^)，空间复杂度O(n^2^)

//w[i][j]表示i到j的最小路径,初始化时，邻接则填入邻接距离，否则填入Inf
for(int k = 0;k< w.length;k++){
    //中间点
    for(int i =0;i<w.length;i++){
        //起点
        for(int j =0;j<w.length;j++){
            //终点
            w[i][j] = Math.min(w[i][j],w[i][k]+w[k][j]);
        }
    }
}

注意是根据中间点为重心进行循环，先遍历中间点

3015. 按距离统计房屋对数目 I

class Solution {
    public int[] countOfPairs(int n, int x, int y) {
        int inf = Integer.MAX_VALUE/2-100;
        int[][] w = new int[n+1][n+1];
        for(int i =0;i<w.length;i++){
            Arrays.fill(w[i],inf);
        }
        for(int i =1;i<w.length-1;i++){
            w[i][i]=0;
            w[i+1][i+1] = 0;
            w[i][i+1] = 1;
            w[i+1][i] = 1;
        }

        if(x!=y){
            w[x][y] = 1;
            w[y][x] = 1;
        }


        for(int k = 0;k< w.length;k++){
            //中间点
            for(int i =0;i<w.length;i++){
                //起点
                for(int j =0;j<w.length;j++){
                    //终点
                    w[i][j] = Math.min(w[i][j],w[i][k]+w[k][j]);
                }
            }
        }

        int[] res = new int[n];

        for(int i =0;i<w.length;i++){
            for(int j =0;j<w.length;j++){
                if(w[i][j]-1>=0 && w[i][j]-1<res.length){
                    res[w[i][j]-1] ++;
                }
            }
        }

        return res;

    }
}

Dijkstra

求出的是单源最短路，且权值非负。

朴素：时间复杂度O(n^2^)，空间复杂度O(n^2^)

基本思路：分为已确定的点与未确定的点，每一轮拿最小dis终点当作确定点，并查看可否经过这个确定点走到未确定点可以路径更短

//path[i][j]表示从i到j的路径,邻接则是邻接距离，否则为Inf
long[] dis = new long[n];
Arrays.fill(dis,Long.MAX_VALUE/2);
dis[0]=0;
//dis[i]表示从0-i的最短距离，初始化时都填入Inf,dis[0]=0
boolean[] done = new boolean[n];
Arrays.fill(done,false);
//done[i]==true 表示dis[i]已经是最短路径了

while (true){
    int x = -1;
    for(int i =0;i<n;i++){
        if(!done[i] && (x<0 || dis[i]<dis[x])){
            //dis[i]没有定下，并且要找到最小的那个确定下来
            x=i;
        }
    }
    //定下,现在dis[x]是最小的dis
    done[x]=true;

    for(int i =0;i<n;i++){
        //i为终点，x为中间，看能不能更新
        long newDis = dis[x] + path[x][i];

        if(newDis<dis[i]){
            //能更新
            dis[i] = newDis;
        }
    }

}

堆优化

时间复杂度：O(n*logn)，如果是稠密图，则是O(n^2^ *logn)。空间复杂度：O(n)

相同思路，只不过寻找最小dis交给最小堆实现，从而查询一次的复杂度由O(n)到O(logn)

存入堆的是一个二元组（dis,x)表示从0-x的距离为dis

只有第一次出堆是最小dis

因而取消了done，并且由path变为邻接图

//注意：这里是邻接图
ArrayList<int[]>[] neighbour = new ArrayList[n];
for(int i =0;i<neighbour.length;i++){
    neighbour[i] = new ArrayList<>();
}

long[] dis = new long[n];
Arrays.fill(dis,Long.MAX_VALUE/2);
dis[0]=0;
//dis[i]表示从0-i的最短距离，初始化时都填入Inf,dis[0]=0

PriorityQueue<Pair> queue = new PriorityQueue<>(Comparator.comparingLong(Pair::getDx));
queue.add(new Pair(0L,0));

while (true){
    Pair curPair = queue.poll();
    long dx = curPair.getDx();
    int x = curPair.x;

    //初次出堆，才是最小
    if(dx > dis[x])continue;//以前出堆过
    
    if(x==n-1) break;

    for(int[] nei : neighbour[x]){
        int y = nei[0];
        int cur_dis = nei[1];

        long newDis = dx + cur_dis;

        if(newDis < dis[y]){
            dis[y] = newDir;
            queue.add(new Pair(dis[y],y));
        }

    }
}


private class Pair{
    private long dx;
    private int x;
    public Pair(long dx,int x){
        this.dx = dx;
        this.x = x;
    }

    public long getDx(){
        return dx;
    }

    public int getX(){
        return x;
    }

}