$$\color{Red}{Dijkstra-三种语言实现+稀疏稠密全解析}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

1.时间复杂度方面
稠密图：总的时间复杂度为O(n^2)
稀疏图：总的时间复杂度为O(mlogn)

2.算法原理

每次找寻当前距离起点最近的点，并用它更新所有和它相邻的节点距离起点的距离，然后把这个节点置true锁定，
找寻下一个到全部结束为止

3.算法细节

1.稠密图：

对于图论的稠密图，建立邻接表和队列效率往往大打折扣，所以我们使用邻接矩阵完成建图 g[a][b] = min(g[a][b], c);
而对于找寻当前最短可用点，采用t=-1预处理可以避免第一个点的边界 int t = -1;

for(int j=1; j<=n; j++)
    if(!st[j] && (t == -1 || dist[t] > dist[j]))    t = j;

据此我们根据它更新所有点到起点的最短距离

for(int j=1; j<=n; j++)
    dist[j] = min(dist[j], g[t][j] + dist[t]);

全部更新完毕还要进行锁定操作 st[t] = true;

java 稠密图

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 510, n, m;
    static boolean[] st = new boolean[N];
    static int[] d = new int[N];
    static int[][] g = new int[N][N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void dijkstra() {
        d[1] = 0;
        for (int i = 0; i < n - 1; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++)
                if (!st[j] && (t == -1 || d[j] < d[t]))
                    t = j;
            st[t] = true;
            for (int j = 1; j <= n; j++) 
                d[j] = Math.min(d[j], g[t][j] + d[t]);
        }
        if(d[n] == 0x3f3f3f3f) System.out.println(-1);
        else System.out.println(d[n]);
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        Arrays.fill(d, 0x3f3f3f3f);
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) 
            Arrays.fill(g[i], 0x3f3f3f3f);
        for (int i = 0; i < m; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int w = Integer.parseInt(s2[2]);
            g[a][b] = Math.min(g[a][b], w);
        }
        dijkstra();
    }
}

2.稀疏图：

稀疏图的建立就可以正常使用邻接表和队列//无效点少，每次更新往往都具有意义，从而我们引出堆优化版dijksra算法
我们之前找寻最小点O(n2)的复杂度效率很低//如果应用一个小根堆，每次只需要弹出堆顶元素，就优化到了O（1）！
此前每找到最小的点更新全部的点//但点的更新只会影响到它的邻点和邻点后的点，应用队列可以完美解决这些问题
此为正常小根堆的建立方法（优先队列是大根堆）
priority_queue <pii, vector<pii>, greater<pii>> heap;
同时pii的排序，根据第一个元素进行排序，加入堆的操作应该以dist距离作为第一位数字`heap.push({0,1});`

java 稀疏图 使用ProrityQueue

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    static int N = 150010, n, m, idx;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int[] w = new int[N];

    static boolean[] st = new boolean[N];
    static int[] d = new int[N];

    static void add(int x, int y, int z) {
        e[idx] = y;
        ne[idx] = h[x];
        w[idx] = z;
        h[x] = idx++;
    }
    static class Node implements Comparable<Node> {
        int num, dis;

        @Override
        public int compareTo(Node o) {
            return this.dis - o.dis;
        }

        public Node(int num, int dis) {
            this.num = num;
            this.dis = dis;
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void dijkstra() {
        d[1] = 0;
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        q.add(new Node(1, 0));
        while(!q.isEmpty()){
            Node t = q.remove();
            int num = t.num;
            int dis = t.dis;
            if (st[num]) continue;
            st[num] = true;
            for (int i = h[num]; i != -1; i=ne[i]) {
                int son = e[i];
                if (d[son] > dis + w[i]){
                    d[son] = dis + w[i];
                    q.add(new Node(son, d[son]));
                }
            }
        }
        if (d[n] == 0x3f3f3f3f) System.out.println(-1);
        else System.out.println(d[n]);
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        Arrays.fill(d, 0x3f3f3f3f);
        Arrays.fill(h, -1);
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 0; i < m; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int w = Integer.parseInt(s2[2]);
            add(a, b, w);
        }
        dijkstra();
    }
}

出现更小的时候更新最近距离和稠密图逻辑无异dist[x] = dist[ver] + w[i];

1. python3代码(稠密图)

#稠密图所以使用邻接矩阵
N = 510
d = [0x3f3f3f3f] * N
st = [0] * N
g = [[0x3f3f3f] * N for i in range(N)]

def dijkstra():
    d[1] = 0
    for i in range(n-1): #找寻n-1次
        t = -1
        #找寻最近可选点
        for j in range(1, n+1):
            if (not st[j]) and (t == -1 or d[t] > d[j]):
                t = j
        st[t] = True
        #利用它更新每个点
        for j in range(1, n+1):
            d[j] = min(d[j], g[t][j] + d[t])
    if d[n] == 0x3f3f3f3f:
        return -1
    else:
        return d[n]

if __name__ == '__main__':
    n, m = map(int, input().split())
    for i in range(m):
        x, y, z = map(int, input().split())
        g[x][y] = min(g[x][y], z)

    print(dijkstra())

2. C++代码（稠密图）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510;
int g[N][N], dist[N];
int n, m;
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    //n个点，所以我们要找n次最小点，让它再把剩余点逐一更新
    for(int i=1; i<=n; i++)
    {
        //类似先把最大值赋值0x3f，保证能满足
        //与之比较的第一个点必大于他
        int t = -1;

        //从头找到尾第一个未锁定最小值的最小的dist[t]
        for(int j=1; j<=n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j;

        //让他到起点的距离，来更新所有点到起点的距离
        for(int j=1; j<=n; j++)
            dist[j] = min(dist[j], g[t][j] + dist[t]);
        //当彻底更新完后，我们就可以锁死该点的状态
        st[t] = true;
    }

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

int main()
{

    scanf("%d%d", &n, &m);
    //更新所有邻接矩阵的值为无穷
    //这样第一次更新它就不需要特判，直接用min（）
    memset(g, 0x3f, sizeof g);
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        g[a][b] = min(g[a][b], c);
    }
    cout << dijkstra() << endl;

    return 0;
}

3.ptthon3 优先队列优化

from queue import PriorityQueue
N = int(2e5+10)
d = [0x3f3f3f3f] * N
st = [0] * N
h = [-1] * N
e = [0] * N
ne = [0] * N
w = [0] * N #有距离的概念，邻接表中引入一个代表距离的数组
idx = 0

def add(a, b, c):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    w[idx] = c
    h[a] = idx 
    idx += 1

def Dijkstra():
    d[1] = 0
    q = PriorityQueue()
    q.put((0, 1))
    while q.qsize():
        t = q.get()
        ver, distance = t[1], t[0]
        if st[ver]: continue
        #找到可用点后置True
        st[ver] = True
        #遍历邻点
        i = h[ver]
        while i != -1:
            j = e[i]
            if d[j] > distance + w[i]:
                d[j] = distance + w[i]
                q.put((d[j], j))
            i = ne[i]

    if d[n] == 0x3f3f3f3f:    return -1
    else:   return d[n]

if __name__ == '__main__':
    n, m = map(int, input().split())
    for i in range(m):
        a, b, c = map(int, input().split())
        add(a, b, c)
    print(Dijkstra())

4.C++ 稀疏图堆优化

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair <int,int> pii;
const int N = 1e6 + 10;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

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

int dijkstra()
{
    priority_queue <pii, vector<pii>, greater<pii>> heap;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    //这里先把距离写在前，是为了保持维护最近点的小根堆
    heap.push({0,1});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;
        if(st[ver]) continue;

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

            //这里要牢记w[i]的含义
            //我们插入a指向b的点的时候，赋予了对应w[idx]对应的idx值
            //指的是该条链表对应的点指向ne[idx]这个点的权值
            //同时我们使用队列一方面o（1）取最小，而且赋值点也是有意义的邻接点

            if(dist[x] > dist[ver] + w[i])
            {
                dist[x] = dist[ver] + w[i];
                heap.push({dist[x], x});
            }
        }
        //每当使用一个最近点更新完邻接点距离，就锁死它
        //这部在判断是否调用过写也可以，但是写在末尾逻辑更加连贯
        st[ver] = true;
    }

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

int main()
{
    scanf("%d%d", &n, &m);

    int a, b, c;
    memset(h, -1, sizeof h);

    while(m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    cout << dijkstra() << endl;
    return 0;
}