引言

\(Dijkstra\) 算法是用来解决单源正权最短路问题的算法。

原理

进行 \(n\)（\(n\)为顶点的个数）次迭代去确定每个点到起点的最小值最后输出的终点的即为我们要找的最短路的距离。

每次迭代的过程中我们都先找到当前未确定的最短距离的点中距离最短的点。

然后用这个去更新其余未确定点的最短距离。

进行 \(n\) 次迭代后最后就可以确定每个点的最短距离。

即：

循环n - 1次
	找一个结点t，是不在S中的距离最近的点
	将t加入到S里
	用t更新其它点的距离

示例

假设有如下的图：

这里用到了一个画图网站（挺好玩的）：https://csacademy.com/app/graph_editor/

假设从顶点 \(1\) 开始，找顶点 \(1\) 到其他点的最短距离，过程如下：

首先将其他的距离设为 \(∞\)，顶点 \(1\) 到自己的距离设置为 \(0\)

这里用 \(dist[i]\) 表示顶点 \(1\) 到 \(i\) 的距离

顶点	集合 \(S\)	\(2\)	\(3\)	\(4\)
第 \(1\) 轮	\(\{1\}\)	\(2\) \(v_1 \rightarrow v_2\)	\(5\) \(v_1 \rightarrow v_3\)	\(4\) \(v_1 \rightarrow v_4\)
第 \(2\) 轮	\(\{1,2\}\)	\(2\)	\(4\) \(v_1 \rightarrow v_2 \rightarrow v_3\)	\(3\) \(v_1 \rightarrow v_2 \rightarrow v_4\)
第 \(3\) 轮	\(\{1,2,4\}\)	\(2\)	\(4\) \(v_1 \rightarrow v_2 \rightarrow v_3\)	3
第 \(4\) 轮	\(\{1,2,3,4\}\)	\(2\)	4	3

朴素版 \(Dijkstra\)

时间复杂度：\(O(n^2)\)

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

using namespace std;

const int N = 510;

int n, m;
int g[N][N]; // g[i][j] 表示 i 到 j 顶点的边的权重
int dist[N]; // 表示初始点距离目前点的距离
bool st[N]; // st 表示是否将该点加入集合

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[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 || dist[t] > dist[j]))
                t = j;

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

        st[t] = true;
    }

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

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

    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);
    }

    printf("%d\n", dijkstra());

    return 0;
}

堆优化

寻找新结点的操作，可以使用优先队列代替，之后遍历当前新结点的每条边更新距离，所以时间复杂度为 \(O(mlogn)\)

堆优化版 \(Dijkstra\)

时间复杂度：\(O(mlogn)\)

#include <bits/stdc++.h>
#define N 1000010
#define pii std::pair<int,int>

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

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

void dijkstra() {
	memset(dist,0x3f,sizeof dist);

	dist[s] = 0;

	std::priority_queue<pii,std::vector<pii>,std::greater<pii>> heap;

	heap.push({0,s});

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

		int v = p.second, d = p.first;

		if(st[v]) continue;
		st[v] = true;

		for (int i = h[v] ; i != -1 ; i = ne[i]) {
			int j = e[i];
			if(dist[j] > d + w[i]) {
				dist[j] = d + w[i];
				heap.push({dist[j],j});
			}
		}
	}

	return ;
}

int main() {
	std::cin >> n >> m >> s;

	memset(h,-1,sizeof h);

	while(m -- ) {
		int a,b,c;
		std::cin >> a >> b >> c;
		add(a,b,c);
	}

	dijkstra();

	return 0;
}