前言和模板
参考文档
第一次接触$Dijkstra$是在大一下复习数据结构期末考试看了下思路。现在刚开始大二下，打卡群写kuangbin专题最短路不得不学下$Dijkstra$🤣，事实证明（1）我很懒（2）人的潜力不容小觑，我曾以为自己永远也看不懂与图相关的算法。
再说下$Dijkstra$的适用前提：
- 带权图的最短路径
- 权值都为非负值
- 单点出发到其它点
言归正传，直接上蒟蒻总结的模板吧。
（1）稠密图
直接用邻接数组的形式存
//从1到n的最短距离
int dij()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; //含义是到自身的距离为0
//大循环只是计次数
for(int _ = 0; _ < n; ++ _)
{
int t = -1; //寻找当前的最短路
for(int i = 1; i <= n; ++ i)
if(!b[i] && (t == -1 || dist[t] > dist[i])) //短路原则
t = i;
//t是所有未到达的点中的最短路
b[t] = true;
//尝试更新距离数组
for(int i = 1; i <= n; ++ i)
if(dist[t] + a[t][i] < dist[i])
dist[i] = dist[t] + a[t][i];
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}（2）稀疏图
稀疏图的节点数可高达$10^5$，这个时候用朴素$Dijkstra$算法一定超时。于是堆优化版的$Dijkstra$算法诞生了。
为什么可以用堆优化？我们发现朴素版的“寻找当前的最短路”和“尝试更新距离”部分是从$1$到$n$硬跑一遍，这一步骤是稀疏图超时的原因。而堆的完全二叉树特性将“找寻当前最短路“的时间复杂度压缩成$log(n)$。
使用邻接链表存储边与边的权值
//求1到n的最短距离
//一个点能被更新的前提是它的前驱被更新
int dij(int n)
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q; //需要小根堆依据距离排序
q.push({0, 1});
while(q.size())
{
auto tt = q.top(); q.pop();
int t = tt.second;
if(b[t]) continue;
b[t] = true;
//更新这个点的后继
for(int i = 0; i < a[t].size(); ++ i)
{
int newnode = a[t][i].first, val = a[t][i].second;
if(dist[newnode] > dist[t] + val)
{
dist[newnode] = dist[t] + val;
q.push({dist[newnode], newnode}); //距离 节点
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}例题 点击题目跳转链接
例一、Dijkstra求最短路 I
板子题，题面不再赘述。
参考代码1 朴素Dijkstra
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int a[N][N];
int dist[N];
bool b[N];
int n, m;
//从1到n的最短距离
int dij()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int _ = 0; _ < n; ++ _)
{
int t = -1;
for(int i = 1; i <= n; ++ i)
if(!b[i] && (t == -1 || dist[t] > dist[i]))
t = i;
b[t] = true;
for(int i = 1; i <= n; ++ i)
if(dist[t] + a[t][i] < dist[i])
dist[i] = dist[t] + a[t][i];
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
ios::sync_with_stdio(false);
memset(a, 0x3f, sizeof a);
cin >> n >> m;
int x, y, z;
for(int i = 0; i < m; ++ i)
{
cin >> x >> y >> z;
a[x][y] = min(a[x][y], z);
}
cout << dij();
return 0;
}参考代码2 堆版本（稠密图不需要堆优化，演示下堆怎么写）
//从1到n的最短距离
int dij()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q; //距离 下标
q.push({0, 1});
while(q.size())
{
auto tt = q.top(); q.pop();
int t = tt.second;
if(b[t]) continue;
b[t] = true;
for(int i = 1; i <= n; ++ i)
{
int newnode = i, val = a[t][i];
if(dist[newnode] > dist[t] + val)
{
dist[newnode] = dist[t] + val;
q.push({dist[newnode], newnode});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}例二、Dijkstra求最短路 II
和例一不同的是结点数高达$10^5$，此时用图的存储方式将由邻接矩阵变为邻接链表
堆优化版代码（不能用朴素法）
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5e4 + 5;
typedef pair<int, int> PII;
int dist[N];
vector<vector<PII>> a;
bool b[N];
int dij(int n)
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q; //需要小根堆依据距离排序
q.push({0, 1});
while(q.size())
{
auto tt = q.top(); q.pop();
int t = tt.second;
if(b[t]) continue;
b[t] = true;
for(int i = 0; i < a[t].size(); ++ i)
{
int newnode = a[t][i].first, val = a[t][i].second;
if(dist[newnode] > dist[t] + val)
{
dist[newnode] = dist[t] + val;
q.push({dist[newnode], newnode});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
ios::sync_with_stdio(false);
int n, m; cin >> n >> m;
a.resize(n + 1);
int x, y, z;
for(int i = 0; i < m; ++ i)
{
cin >> x >> y >> z;
a[x].push_back({y, z});
}
cout << dij(n);
return 0;
}例三、货物运输
写了两个裸题后再来一道非裸题结个尾吧
题目
给定一个 n 个点 m 条边的无重边无自环的无向图。点的编号为 1∼n。
现在，要从点 1 到点 n运货。
已知每条边的最大承重，请你计算一次最多可以运多少货物。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 n,m。
接下来 m 行，每行三个整数 a,b,c，表示点 a 和点 b 之间有一条无向边，最大承重为 c。
输出格式
每组数据先输出一行 Scenario #x，其中 x 是组别编号（从 1 开始）。
然后一行，输出一个整数，表示一次性最多可运货物数量。
最后输出一个空行。
数据范围
$1≤T≤10,$
$1≤n≤1000,$
$1≤m≤\frac{n(n−1)}{2}$,
$1≤a,b≤n,$
$1≤c≤10^6$。
保证一定有解。
输入样例：
1
3 3
1 2 3
1 3 4
2 3 5输出样例：
Scenario #1:
4问题分析
- 权值都非负且问题和"最短路"相关，用$Dijkstra$算法
- 求的值是所有路径中最小值集合的最大值
- $dist$数组存最小的承重量即可，越大越好
参考代码1 朴素Dijkstra
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1005;
int a[N][N];
int dist[N];
bool b[N];
int dij(int n)
{
dist[1] = 2e9;
for(int _ = 0; _ < n; ++ _)
{
int t = -1;
for(int i = 1; i <= n; ++ i)
if(!b[i] && (t == -1 || dist[t] < dist[i]))
t = i;
b[t] = true;
for(int i = 1; i <= n; ++ i)
if(dist[i] < min(dist[t], a[t][i]))
dist[i] = min(dist[t], a[t][i]);
}
return dist[n];
}
int main()
{
ios::sync_with_stdio(false);
int T, n, m; cin >> T;
for(int i = 1; i <= T; ++ i)
{
memset(a, 0, sizeof a);
memset(dist, 0, sizeof dist);
memset(b, 0, sizeof b);
int n, m; cin >> n >> m;
int x, y, z;
for(int _ = 0; _ < m; ++ _)
{
cin >> x >> y >> z;
a[x][y] = a[y][x] = z;
}
cout << "Scenario #" << i << ":" << endl;
cout << dij(n) << endl << endl;
}
return 0;
}参考代码2 堆版本
int dij(int n)
{
priority_queue<PII> q; //从1到n越大越好
q.push({2e9, 1});
while(q.size())
{
auto [v, t] = q.top(); q.pop();
if(b[t]) continue;
b[t] = true;
for(int i = 1; i <= n; ++ i)
{
if(min(v, a[t][i]) > dist[i]) //当前承重和新的承重
{
dist[i] = min(v, a[t][i]);
q.push({dist[i], i});
}
}
}
return dist[n];
}总结
- 模板写在了开头
- 求最短路时要注意题意是最大值还是最小值；相加还是取最小（大）值
- 最小值用小根堆；最大值用大根堆