Dijkstra 朴素版最短路径 对稠密图进行存储 通过邻接矩阵的方式进行存储

• 初始化dist[i]表示节点i与源点之间的距离 初始化邻接举证0x3f3f3f
• 对于n个节点重复n次操作 for(int k=0;k<n;k++){

}
+ 重所有的未选中的节点中选出dist[]离源点最近的节点
+ 将该节点加入集合
+ 通过该点更新相邻的节点dist[]

import java.util.*;

public class Main{
    static int N=510;
    static int[][] g=new int[N][N];
    //距离数组
    static int[] dist=new int[N];
    //集合数组
    static boolean[] vis=new boolean[N];

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int m=sc.nextInt();
        for(int i=1;i<=n;i++){
            Arrays.fill(g[i],0x3f3f3f);
        }
        for(int i=0;i<m;i++){
            int a=sc.nextInt();int b=sc.nextInt();int c=sc.nextInt();
            g[a][b]=Math.min(g[a][b],c);
        }
        int res=dijkstra(n);

        System.out.println(res);
    }
    public static int dijkstra(int n){
        Arrays.fill(dist,0x3f3f3f);
        dist[1]=0;

        for(int k=0;k<n;k++){
                int t=-1;
                for(int i=1;i<=n;i++){
                    if(!vis[i]&&(t==-1||dist[t]>dist[i])){
                        t=i;
                    }
                }
                vis[t]=true;
                //更新其他的节点
                for(int i=1;i<=n;i++){
                    // if(!vis[i]&&dist[i]>dist[t]+g[t][i]){
                    //     dist[i]=dist[t]+g[t][i];
                    // }
                    dist[i]=Math.min(dist[i],dist[t]+g[t][i]);
                }     
        }

        if(dist[n]==0x3f3f3f){
            return -1;
        }
        return dist[n];
    }
}

通过堆优化的方式对 稀疏图（通过邻接表进行存储）

//堆优化的最短路dijkstra通过邻接表的方式存储
import java.util.*;

public class Main{
    static int N=510,M=100010;
    static int[] h=new int[N];static int[] e=new int[M];static int[] ne=new int[M];static int[] w=new int[M];
    static int idx=0;
    static int[] dist=new int[N];
    static boolean[] vis=new boolean[N];

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int m=sc.nextInt();
        Arrays.fill(h,-1);
        Arrays.fill(dist,0x3f3f3f);
        for(int i=0;i<m;i++){
            int a=sc.nextInt();int b=sc.nextInt();int c=sc.nextInt();

            add(a,b,c);
        }

        int res=dijkstra(n);
        System.out.println(res);

    }

    public static int dijkstra(int n){
        PriorityQueue<int[]> heap=new PriorityQueue<int[]>((a,b)->a[0]-b[0]);
        dist[1]=0;
        heap.offer(new int[]{0,1});
        while(!heap.isEmpty()){
            int[] node=heap.poll();

            int ver=node[1];int distance=node[0];

            if(vis[ver]){
                continue;
            }
            vis[ver]=true;

            for(int i=h[ver];i!=-1;i=ne[i]){
                int j=e[i];
                if(dist[j]>distance+w[i]){
                    dist[j]=distance+w[i];
                    heap.offer(new int[]{dist[j],j});
                }
            }

        }
        if(dist[n]==0x3f3f3f){
            return -1;
        }
        return dist[n];
    }

    public static void add(int a,int b,int c){
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}

prim稠密图 g[][] 最小生成树

import java.util.*;
public class Main{
    static int N=510;
    static int[][] g=new int[N][N];
    static boolean[] vis=new boolean[N];
    static int[] dist=new int[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int m=sc.nextInt();
        for(int i=1;i<=n;i++){
            Arrays.fill(g[i],0x3f3f3f);
        }
        for(int i=0;i<m;i++){
            int a=sc.nextInt();int b=sc.nextInt();int c=sc.nextInt();
            g[a][b]=g[b][a]=Math.min(g[a][b],c);
        }
        int res=prim(n);
        if(res==0x3f3f3f){
            System.out.println("impossible");
        }else{
         System.out.println(res);   
        }
    }

    public static int prim(int n){
        Arrays.fill(dist,0x3f3f3f);
        int res=0;
        for(int k=0;k<n;k++){
            int t=-1;
            for(int i=1;i<=n;i++){
                if(!vis[i]&&(t==-1||dist[i]<dist[t])){
                    t=i;
                }
            }
            if(t!=1&&dist[t]==0x3f3f3f){
                return 0x3f3f3f;
            }

            if(t!=1){
                res+=dist[t];
            }

            for(int i=1;i<=n;i++){
                dist[i]=Math.min(dist[i],g[t][i]);
            }

            vis[t]=true;
        }
        return res;
    }

}

通过kruskal 稀疏图 最小生成树

import java.util.*;

public class Main{
    static PriorityQueue<int[]> queue=new PriorityQueue<int[]>((a,b)->a[0]-b[0]);
    static int N=100010;
    static int[] father=new int[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int m=sc.nextInt();
        init(n);
        for(int i=0;i<m;i++){
            int a=sc.nextInt();int b=sc.nextInt();int c=sc.nextInt();
            queue.offer(new int[]{c,a,b});
        }
        int res=0;int cnt=0;
        for(int i=1;i<=m;i++){
            int[] node=queue.poll();
            int a=node[1];int b=node[2];int c=node[0];
            if(find(a)!=find(b)){
                cnt++;
                res+=c;
                father[find(a)]=find(b);
            }
        }
        if(cnt<n-1){
            System.out.println("impossible");
        }else{
         System.out.println(res);   
        }
    }

    public static void init(int n){
        for(int i=1;i<=n;i++){
            father[i]=i;
        }
    }

    public static int find(int x){
        if(x!=father[x]){
            father[x]=find(father[x]);
        }
        return father[x];
    }

}

应用kruskal

对应的距离定义为哈密顿距离
连接所有点的最小费用

class Solution {
    int[] father;
    public int minCostConnectPoints(int[][] points) {
        PriorityQueue<int[]> queue=new PriorityQueue<int[]>((a, b)->a[0]-b[0]);
        int n=points.length;
        father=new int[n];
        init(n);
        int cnt=0;int res=0;
        int m=n*(n-1)/2;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int dist=getDist(points[i],points[j]);
                queue.offer(new int[]{dist,i,j});
            }
        }
        for(int i=1;i<=m;i++){
            int[] node=queue.poll();
            int a=node[1];int b=node[2];int c=node[0];
            if(find(a)!=find(b)){
                cnt++;
                res+=c;
                father[find(a)]=find(b);
            }
        }
        return res;
    }

    public void init(int n){
        for(int i=0;i<n;i++){
            father[i]=i;
        }
    }

    public int find(int x){
        if(x!=father[x]){
            father[x]=find(father[x]);
        }
        return father[x];
    }

    public int getDist(int[] start,int[] end){
        return Math.abs(start[0]-end[0])+Math.abs(start[1]-end[1]);
    }
}