笔记——最短路径Dijkstra算法
第一步
定义数组和变量：
int f[101][101]; //将得到的数据转化成邻接矩阵
int ans[101]; //用来记录答案（从1到各点的最短路径）
int q1[105],l=0,r=1; //队列，详见《笔记——栈，队列，快速幂，线性筛，并查集，随机数》
bool YN[101]; //记录一个点是否入队
然后初始化：
for(re int i=1;i<=n;++i){
YN[i]=false;
for(re int j=1;j<=n;++j){
if(i!=j)
f[i][j]=MAXint;
else
f[i][j]=0;
}
}
第二步
假设我们得到了一个这样子的图和数据
点数：6
边数：9
每条边相连的点以及边的权值：
1 2 7 //意思是：点1和点2之间有一条线，权值为7
1 3 9
1 6 14
2 4 15
2 3 10
3 6 2
3 4 11
6 5 9
4 5 6
将得到的点数，边数，每条边相连的点以及边的权值存下来
re int n,m;
cin>>n>>m;
re int a,b,q;
for(re int i=1;i<=m;++i){
cin>>a>>b>>q;
f[a][b]=f[b][a]=q;
}
第三步
经过初始化，读入后，我们就要开始分析计算方法了，首先，写出一个表格
| F | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 0 | 7 | 9 | ∞ | ∞ | 14 |
| 2 | 7 | 0 | 10 | 15 | ∞ | ∞ |
| 3 | 9 | 10 | 0 | 11 | ∞ | 2 |
| 4 | ∞ | 15 | 11 | 0 | 6 | ∞ |
| 5 | ∞ | ∞ | ∞ | 6 | 0 | 9 |
| 6 | 14 | ∞ | 2 | ∞ | 9 | 0 |
因为我们是求每个点到1的最短距离，所以我们把ans的值赋为f[1][i]
代码：
for(re int i=1;i<=n;++i)
ans[i]=f[1][i];
接着我们来分析一下解题方法
首先让1进队q1[r]=1,++r;并且把YN[i]赋值为true表示已经进过队列了，防止重复进队，重复搜索。
然后从1开始搜索，搜索到所有与1相连并且没有进过队列的点，可以得到分别是2,3,6，然后依次将他们推进队列，然后队列里是这样的：
| 1（队头） | 2 | 3 | 6（队尾） |
|---|
接着将YN[2,3,6]都设置为true
现在，到了最重要的部分了，如何计算这个点到1的最短路？
我们知道，是求最短路，所以先拿出min函数，因为ans数组里已经在初始化时有了部分数据，所以我们也要和原来在ans数组里的数与现在这个数到下一个数的距离+这个数到1的距离比较，把ans赋值为两者之间最小的一个（可能有点难听懂，你也可以直接跳过往下看举例）
举例：
如何求1到5的最短路？
我们可以从1开始搜索，1可以到达2,3,6，ans是这样的：
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 7 | 9 | ∞ | ∞ | 14 |
然后把1退出队列，搜索2
2可以到达3,4（因为YN[1]的值已经为true了，所以不算进去），我们把4推进队列，2到3的距离为10，到4的距离是15，于是我们重新计算1到3,4的最小值，目前知道以下两个路线：
- 到3
- 1—>3 距离为ans[3]=9（也就是1到3的距离）
- 1—>2—>3 距离为ans[2]+f[2][3]=7+10=17（也就是1到2的距离+2到3的距离）
比较两个距离大小，9<17，所以将ans[3]赋值为9
- 到4
- 1—>4 距离为ans[4]=∞（也就是1到4的距离）
- 1—>2—>4 距离为ans[2]+f[2][4]=7+15=22（也就是1到2的距离+2到4的距离）
比较两个距离大小，22<∞，所以将ans[4]赋值为22
于是经过这一波计算，ans数字变成了这样
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 7 | 9 | 22 | ∞ | 14 |
然后把2推出队列，搜索3
队列就成了这样
| 3 | 6 | 4 |
|---|
3可以到达4,6，距离分别是11和2，目前知道以下两个路线：
- 到4
- 1—>4 距离为ans[4]=22（也就是1到4的距离）
- 1—>3—>4 距离为ans[3]+f[3][4]=9+11=20（也就是1到3的距离+3到4的距离）
比较两个距离大小，20<22，所以将ans[4]赋值为20
- 到6
- 1—>6 距离为ans[6]=14（也就是1到6的距离）
- 1—>3—>6 距离为ans[3]+f[3][6]=9+2=11（也就是1到3的距离+3到6的距离）
-
比较两个距离大小，11<14，所以将ans[6]赋值为11
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 7 | 9 | 20 | ∞ | 11 |
以此类推，经过重复计算，我们可以得到1到每个点的最短路了
程序：
while(l<=r){
re int now=q1[l];
for(re int i=1;i<=n;++i){
if(f[now][i]!=MAXint&&f[now][i]!=0){
if(YN[i]==false) q1[r]=i,++r,YN[i]=true;
ans[i]=min(ans[i],f[now][i]+ans[now]);
}
}
++l;
}
第四步
输出答案
for(re int i=1;i<=n;++i){
cout<<ans[i]<<" ";
}
总结：
程序：
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("abm,avx,avx2,mmx,popcnt,sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define in inline
#define re register
using namespace std;
int f[101][101];
int ans[101];
int q1[105],l=0,r=1;
bool YN[101];
const int MAXint=2147483647;
int main(){
re int n,m;
cin>>n>>m;
for(re int i=1;i<=n;++i){
YN[i]=false;
for(re int j=1;j<=n;++j){
if(i!=j)
f[i][j]=MAXint;
else
f[i][j]=0;
}
}
re int a,b,q;
for(re int i=1;i<=m;++i){
cin>>a>>b>>q;
f[a][b]=f[b][a]=q;
}
q1[r]=1,++r;
YN[1]=true;
for(re int i=1;i<=n;++i)
ans[i]=f[1][i];
while(l<=r){
re int now=q1[l];
for(re int i=1;i<=n;++i){
if(f[now][i]!=MAXint&&f[now][i]!=0){
if(YN[i]==false) q1[r]=i,++r,YN[i]=true;
ans[i]=min(ans[i],f[now][i]+ans[now]);
}
}
++l;
}
for(re int i=1;i<=n;++i){
cout<<ans[i]<<" ";
}
}
本文作者：Andysun06