#最短路径(极简版)__Dijkstra
2025-10-18 16:25:09
发布于：浙江
3阅读
0回复
0点赞
本人第一次发帖
相信Dijkstra最短路径算法大家肯定并不陌生
它的基本思路就是
一般情况下我们要开这些数组
int g[n][n];//这里用邻接矩阵存带权边
int dis[n];//dis[i]表示从起点到第i个点的最短路径
bool vis[n];//标记
int n,m,s,t;//点数，边数，起点，终点
一开始
dis[i],g[i][j]都赋一个较大值,例如inf=0x3f3f3f
步骤：
1.在dis数组中找一个点v（值最小&&未标记）
2.从这个点，向与之相连的点j进行修改（若dis[j]>dis[v]+g[v][j]）
遍历每个点之后
dis[t]就是从s开始到t的最短路径
代码
#include <bits/stdc++.h>
#define maxn 1005
#define inf 0x3f3f3f
using namespace std;
int n,m,s,t;
int g[maxn][maxn];
int dis[maxn];
bool vis[maxn];
int main(){
memset(g,inf,sizeof(g));
memset(dis,inf,sizeof(dis));
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
g[x][y]=z;
}
dis[s]=0;
for(int i=1;i<=n;i++){
int minn=INT_MAX;
int v;
for(int j=1;j<=n;j++){
if(minn>dis[j]&&vis[j]==false){
minn=dis[j];
v=j;
}
}
vis[v]=1;
for(int j=1;j<=n;j++){
if(dis[j]>dis[v]+g[v][j]){
dis[j]=dis[v]+g[v][j];
}
}
}
cout<<dis[t];
return 0;
}
也是非常简洁
这里空空如也
有帮助，赞一个