模拟dijkstra

有向图

一定不能存在负权边

原因:因为在第一次发现最短距离就将其加入st集合中，已经确定了其距离

举例：无法预知未来有一个负边减少其路径长度

起点为a

a到b l = 2;

a到c l =3;

c到b l =-4;

所以模拟dijkstra()算法

得到的结果:首先确定a,然后a到b是最近的，所以再次确定b=2，然后再确定c=3

而错误之处：实际上是a到c =2,a到b是1

朴素版做法 稠密图 m远小于n^2

朴素版做法，适用于稠密图
用邻接矩阵存储边，有重边与自环，无负权边
所以初始化邻接矩阵为最大值
dijkstra():
初始化所有点到1号点的距离是INF,dist[1]=0
for(循环n次){
找到未在st集合中距离1号点最近的点
加入到st集合中
更新其他所有点到1号点的距离
}
判断：如果n号点到1号点的距离等于INF，返回-1
否则返回dist[n]

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;

//学习路径
//https://www.acwing.com/video/24/  42:42
public class Main {
    static int N = 510;//点的范围上限
    static int n, m;//点与边的个数
    static int[][] g = new int[N][N];//权重，边长
    static int[] dist = new int[N];//1号点到每一个点的最小路径
    static boolean[] st = new boolean[N];//是否确定最小路径

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 0; i < N; i++) {
            //0x3f3f3f3f是一个比较大的数，但是不至于经过运算就会超出int数据范围
            Arrays.fill(g[i], 0x3f3f3f3f);
        }
        while (m-- > 0) {
            int a, b, c;
            s = in.readLine().split(" ");
            a = Integer.parseInt(s[0]);
            b = Integer.parseInt(s[1]);
            c = Integer.parseInt(s[2]);
            g[a][b] = Math.min(g[a][b], c);
        }
        int t = dijkstra();
        System.out.println(t);
    }

    static int dijkstra() {
        //初始化1号点到每一个点的距离为正无穷
        Arrays.fill(dist, 0x3f3f3f3f);
        //1号点到自己的距离为0
        dist[1] = 0;
        for (int i=0;i<n;i++){
            int t  =-1;//获得不在st中，距离最近的点
            for (int j=1;j<=n;j++){//遍历点
                //不在st中，距离最近的点
                if (!st[j]&&(t==-1||dist[t]>dist[j])){
                    t =j;
                }
            }
            //将t加入到st,确定最短,逐步贪心
            st[t] = true;
            //用t更新其他点
            for (int j=1;j<=n;j++){
                dist[j] = Math.min(dist[j],dist[t] +g[t][j]);
            }
        }
        //如果1号点到n号的距离还是0x3f3f3f3f，说明，没有最短路，
        //最短路不会是INF，因为题目数据达不到INF
        if (dist[n]==0x3f3f3f3f){
            return -1;
        }
        return dist[n];
    }
}

堆优化做法 稀疏图

因为是稀疏图，所以使用邻接表
初始化表头h为-1
读取数据，加入到邻接表中，e[idx] = b,w[idx] = w,ne[idx] = h[a],h[a] = idx++;
初始化所有点到1号点的距离，dist[1] = 0;
队列存储的是数组，有点编号和点到1号点的距离
堆优化版dijkstra
将1号点加入优先队列（最小堆）中去，
while(判断队列是否为空){
队列弹出最小距离元素（此处比朴素版的时间复杂度低，因为使用的是最小堆，默认弹出最小值）
判断该元素是否已经确认距离 确认跳过
否则，加入到st集合中
ver = t[0]点号
distance=t[1]距离
使用该点去更新其他点的距离int i = h[ver];i!=-1;i=ne[i];
int j =e[i];判断dist[j],是否最优，如果不是最优，更新dist[j],并加入到队列中
q.add(new int{j,dist[j]});//点号，距离
}
判断dist[n]的距离是否等于INF，返回-1
返回 dist[n]

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;

//学习路径
//https://www.acwing.com/video/24/  42:42
public class Main {
    static int N = 1000010;//点的范围上限
    //static PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->{return a[1] - b[1];});//堆
    static PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{return a[1]-b[1];});
    static int n, m,idx=1;//点与边的个数
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] w = new int[N];
    static int[] dist = new int[N];//1号点到每一个点的最小路径
    static boolean st[] = new boolean[N];//是否确定最小路径

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        while (m-- > 0) {
            int a, b, c;
            s = in.readLine().split(" ");
            a = Integer.parseInt(s[0]);
            b = Integer.parseInt(s[1]);
            c = Integer.parseInt(s[2]);
			//因为是邻接表，去除重边需要对每次加入边进行判断，太耗时间，全部加进去
            add(a,b,c);
        }
        int t = dijkstra();
        System.out.println(t);
    }

    static void add(int a,int b,int c){
        e[idx] = b;
        w[idx]=c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static int dijkstra() {
        //初始化1号点到每一个点的距离为正无穷
        Arrays.fill(dist, 0x3f3f3f3f);
        //1号点到自己的距离为0
        dist[1] = 0;
        q.add(new int[]{1,0});
        while (q.size()!=0){
            int[] t = q.poll();
            int ver = t[0];
            int distence = t[1];
            
      //如果已经确定了这个点，至于为什么跳过，又为什么加入到队列中
      //是因为可能c被a加进去队列一次，又被b加进去队列一次，会计算两次，虽然不会影响结果，但是会增加时间复杂度，所以跳过进行优化
            if (st[ver]) continue;
            st[ver] = true;
            for(int i=h[ver];i;i=ne[i]){
                int j = e[i];
                if (dist[j]>distence+w[i]){
                    dist[j] = distence+w[i];
                    //为什么此处不可使用st记录队列中是否具体这项元素而进行代替上面的continue
					//因为第一次加进去的可能不是最优解
                    //而队列其中的数据却无法随着外面dist[j]的修改而修改
                    //比如，在遍历a点周围的点时，将b,c加进去
                    //然后下次遍历b时，应该再次将c加入,因为a-c>a-b + b-c
                    //但是因为a时将c加进去了，所以此处b时并没有将此c加进去而导致下一次计算的时候会使用dist[j],来自a-c
                    //导致后面没有使用到最优解
                    //如果使用此方法，可以int distence = t[1];修改为
                    //int distence = dist[ver];	
                    q.add(new int[]{j,dist[j]});
                }
            }
        }
        //如果1号点到n号的距离还是0x3f3f3f3f，说明，没有最短路，
        //应该少了最短路恰好是0x3f3f3f3f
        if (dist[n]==0x3f3f3f3f){
            return -1;
        }
        return dist[n];
    }
}