一、简述
本节主要介绍一下 \(Dijkstra\) 算法。该算法主要用于解决单源最短路问题，且该问题中的边权不为负数。
二、Dijkstra算法
基本思想：我们假定有一张没有负权的图，该图如下
\(dist\) 数组的元素 \(dist[i]\) 表示从起点到 \(i\) 的距离，初始化为正无穷。假设起点为 \(1\)，那么 \(dist[1]=0\)。然后我们迭代 \(4\) 次。首先我们找到不在集合 \(S\) 中且其距离起点最近的点 \(t\)，将 \(t\) 并入 \(S\) 中，用 \(t\) 来更新到其余点的距离。参考样图，\(dist[1]=0\)，而其余的 \(dist\) 均为正无穷，那么先找到的是 \(1\)，将 \(1\) 并入 \(S\)，对于可以由 \(1\) 的所有出边的点的距离进行松弛，我们可以得到 \(dist[2]=1,dist[3]=4,dist[4]=6\)。然后我们对于不在集合 \(S\) 中且距离起点最近的点为 \(2\)，我们将 \(2\) 并入 \(S\)，对于 \(2\) 的所有出边的点的距离进行松弛，也就是 \(dist[4]=3,dist[5]=5\)。然后就考虑 \(4\)，加入集合 \(S\)，进行松弛。直至所有的点都加入 \(S\)。
对于数据范围较小，且为稠密图的可以使用邻接矩阵进行图的存储，该算法朴素版的时间复杂度为 \(O(n^2)\)。而数据范围大，稀疏图使用邻接表存储，并使用小根堆进行优化，时间复杂度为 \(O(mlogn)\)。
模板题AcWing849.Dijkstra求最短路 I
题目描述
给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 \(1\) 号点到 \(n\) 号点的最短距离，如果无法从 \(1\) 号点走到 \(n\) 号点，则输出 \(−1\)。
输入格式
第一行包含整数 \(n\) 和 \(m\)。
接下来 \(m\) 行每行包含三个整数 \(x,y,z\)，表示存在一条从点 \(x\) 到点 \(y\) 的有向边，边长为 \(z\)。
输出格式
输出一个整数，表示 \(1\) 号点到 \(n\) 号点的最短距离。
如果路径不存在，则输出 \(−1\)。
数据范围
\(1≤n≤500,\)
\(1≤m≤10^5,\)
图中涉及边长均不超过 \(10000\)。
输入样例
3 3
1 2 2
2 3 1
1 3 4
输出样例
3
C++代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n; 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;
else return dist[n];
}
int main()
{
memset(g, 0x3f, sizeof g);
scanf("%d%d", &n, &m);
while(m --)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
g[x][y] = min(g[x][y], z);
}
int ans = dijkstra();
printf("%d\n", ans);
return 0;
}
模板题AcWing850.Dijkstra求最短路 II
题目描述
给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 \(1\) 号点到 \(n\) 号点的最短距离，如果无法从 \(1\) 号点走到 \(n\) 号点，则输出 \(−1\)。
输入格式
第一行包含整数 \(n\) 和 \(m\)。
接下来 \(m\) 行每行包含三个整数 \(x,y,z\)，表示存在一条从点 \(x\) 到点 \(y\) 的有向边，边长为 \(z\)。
输出格式
输出一个整数，表示 \(1\) 号点到 \(n\) 号点的最短距离。
如果路径不存在，则输出 \(−1\)。
数据范围
\(1≤n,m≤1.5×10^5,\)
图中涉及边长均不小于 \(0\)，且不超过 \(10000\)。
数据保证：如果最短路存在，则最短路的长度不超过 \(10^9\)。
输入样例
3 3
1 2 2
2 3 1
1 3 4
输出样例
3
C++代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int N = 200010;
typedef pair<int, int> PII;//first是距离，second是点
#define x first
#define y second
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()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m --)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
}
int ans = dijkstra();
cout << ans << endl;
return 0;
}
三、Dijkstra算法的应用
AcWing1488.最短距离
题目描述
有 \(N\) 个村庄，编号 \(1\) 到 \(N\)。
村庄之间有 \(M\) 条无向道路，第 \(i\) 条道路连接村庄 \(a_i\) 和村庄 \(b_i\)，长度是 \(c_i\)。
所有村庄都是连通的。
共有 \(K\) 个村庄有商店，第 \(j\) 个有商店的村庄编号是 \(x_j\)。
然后给出 \(Q\) 个询问，第 \(k\) 个询问给出一个村庄的编号 \(y_k\)，问该村庄距离最近的商店有多远？
输入格式
第一行包含两个整数 \(N,M\)。
接下来 \(M\) 行，每行包含三个整数 \(a_i,b_i,c_i\)，表示第 \(i\) 条道路连接村庄 \(a_i\) 和村庄 \(b_i\)，长度是 \(c_i\)。
再一行包含整数 \(K\)。
接下来 \(K\) 行，每行包含一个整数 \(x_j\)，表示第 \(j\) 个有商店的村庄编号是 \(x_j\)。
再一行包含整数 \(Q\)。
接下来 \(Q\) 行，每行包含一个整数 \(y_k\)，表示询问编号为 \(y_k\) 的村庄与其距离最近的商店之间的距离。
输出格式
对于每个询问，输出该询问的结果。
数据范围
\(2≤N≤10^5,\)
\(N−1≤M≤min(\frac{N(N−1)}{2},10^5),\)
\(1≤Q≤10^5,\)
\(1≤K≤N,\)
\(1≤c_i≤10000\)
输入样例
7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7
输出样例
3
1
3
0
0
6
0
解题思路
最直接的想法：对于每次询问，我们求出该次询问的起点村庄到所有村庄的最短距离，然后找出这些距离中含有商店的最小距离，那么时间复杂度为 \(O(Qmlogn)\)，必然会超时。那么我们引入一个虚拟点，且该点到所有有商店的村庄的距离为 \(0\)，那么我们就可以从每次从某点出发到商店的最短距离的多源多汇点问题转化为了到从某点到虚拟点的多源单汇点问题，而反过来就是单源最短路问题，也就是从虚拟点到所有村庄的最短距离，这样我们就可以使用 \(Dijkstra\) 算法。
C++代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010, M = 300010;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int dist[N];
int K, Q;
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[0] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 0});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
scanf("%d", &K);
while (K --)
{
int x;
scanf("%d", &x);
add(0, x, 0); // 添加一个虚拟源点
}
dijkstra();
scanf("%d", &Q);
while (Q --)
{
int y;
scanf("%d", &y);
printf("%d\n", dist[y]);
}
return 0;
}