最短路算法自学笔记
2025-03-31 20:24:27
发布于：上海
20阅读
2回复
0点赞
(自学笔记,基本上可以算是抄一些网上的笔记,只是用来记录自己的学习成果,但没有他人的学习价值,甚至可能出现理解错误)
(后期整体学完后,可能会写一些适合学习的笔记,像上篇还没来得及干完的DFS笔记)
最短路算法概念:找出两点之间的最短路距离.
| 概念 | 特点1 | 特点2 | |
|---|---|---|---|
| 单源最短路 | 从任意起点出发,到达固定终点的最短距离 | 未知 | 未知 |
| 多源最短路 | 从任意顶点出发,到达任意重点的最短距离 | 未知 | 未知 |
松弛:
选择一个顶点作为"中转站",经过比较后,更改与其相邻顶点的最短路径值:
单源最短路:
设置数组a:
int a[100];
a[j]用来存储从起点到顶点j的最短距离
单源最短路松弛:
选择一个顶点k作为松弛顶点:(j为路径终点)
w[i,j]代表顶点i到顶点j的权值:
if(a[j]>a[k]+w[k,j])a[j]=a[k]+w[k,j];
多源最短路:
设置数组a:
int a[100][100];
a[i][j]用来存储从顶点i到顶点j的最短距离
多源最短路松弛:
i作为起点,k作为中转站,j作为终点:
if(a[i][j]>a[i][k]+a[k][j])a[i][j]=a[i][k]+a[k][j];
FLOYD(弗洛伊德):
A29680.最短距离查询【Floyd】:
具体思路:
三层循环:
外层:n个顶点枚举(都做一遍松弛)
中层:n个顶点枚举:找出起点(到松弛顶点的起点)
内层:n个顶点枚举:找出中终点(松弛顶点能到的顶点)
#include<bits/stdc++.h>
using namespace std;
int a[205][205];
int main(){
int n,m,k;
cin>>n>>m>>k;
memset(a,0x3f3f3f3f3f,sizeof a);
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
a[x][y]=z;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int z=1;z<=n;z++){
a[j][z]=min(a[j][z],a[j][i]+a[i][z]);
}
}
}
for(int i=1;i<=k;i++){
int x,y;
cin>>x>>y;
if(a[x][y]==int(0x3f3f3f3f3f)){
cout<<"impossible"<<endl;
}else cout<<a[x][y]<<endl;
}
}
Dijkstra:
Gold King的搬家方案:
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Gold{
int zh;
int step;
};
vector<Gold>ST[105];
int dis[105];
bool vis[105];
void dij(){
memset(dis,0x3f3f3f3f,sizeof dis);
dis[1]=0;
for(int i=1;i<=n;i++){
int pos=0;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[pos]>dis[j]){
pos=j;
}
}
//cout<<pos<<endl;
if(!pos)return;
vis[pos]=1;
for(int j=0;j<ST[pos].size();j++){
int poss=ST[pos][j].zh;
dis[poss]=min(dis[poss],dis[pos]+ST[pos][j].step);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
ST[x].push_back({y,z});
ST[y].push_back({x,z});
}
dij();
cout<<dis[n];
}
全部评论 1
你这vis的意义是什么？也没有实现无重边啊
直接用a数组就行，加边代码改成a[x][y] = min(a[x][y], z);（注意memset a数组）
2025-03-20 来自 广东
1
有帮助，赞一个