最短路算法汇总-图论
2025-01-05 19:35:56
发布于：北京
13阅读
0回复
0点赞
一.缔结斯特拉算法
#include <bits/stdc++.h>
using namespace std;
int dis[1100],n,m;
int vis[1100],e[1100][1100];
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
int tmp =e[u][v] ? e[u][v] : 1e9;
e[u][v]=min(w,tmp);
e[v][u]=min(w,tmp);
}
//1 初始化dis
for(int i=0;i<=n;i++){
dis[i]=1e9;
}
dis[1]=0;
//2.n轮 缔结斯特拉
for(int i=1;i<=n ;i++){
int u=0;
//3.1 在没有确定最短路 dis[u] 最小点 u
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]<dis[u]){
u=j;
}
}
//3.2 确定 u 的最短路
vis[u]=1;
//3.3 松弛 u 的邻接边
for(int j=1;j<=n;j++){
if(e[u][j]){
int v=j,w=e[u][j];
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
}
}
}
}
for(int i=2;i<=n;i++){
if(dis[i]!=1e9){
cout<<dis[i]<<endl;
}else{
cout<<1000000000<<endl;
}
}
return 0;
}
二.SPFA
//SPFA
#include<bits/stdc++.h>
using namespace std;
//定义
int n,m,s,t;
int u,v,w;//u有一条到达v权值是w的边
int mp[5050][5050];
int dis[5050];
int vis[5050];//标记一个点在不在队列
int main(){
//输入
cin>>n>>m>>s>>t;
for(int i=1;i<=n;i++){
dis[i]=1e9;
for(int j=1;j<=n;j++){
mp[i][j]=1e9;
}
}
while(m--){
cin>>u>>v>>w;
mp[u][v]=w;
}
//1.搞个队列，起点最短路距离改为0，入队并标记
queue<int>q;
dis[s]=0;
q.push(s);
vis[s]=1;
//2.SPFA 启动！
while(!q.empty()){
//2(1).出队并取消标记
u=q.front();
q.pop();
vis[u]=0;
//2(2).松弛以u为起点的边
for(int i=1;i<=n;i++){
if(mp[u][i]!=1e9){
v=i;
w=mp[u][v];
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
if(vis[v]=1){
q.push(v);
vis[v]=1;
}
}
}
}
}
//输出
cout<<dis[t];
return 0;
}
三.Floyd
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;//计数器
int dis[101][101],*[10001];//距离数组及必经之路数组
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",&*[i]);//输入必经之路
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&dis[i][j]);//输入距离
}
}
//将每个顶点作为中转点
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
//松弛操作
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
}
}
}
for(int i=2;i<=m;i++){
//计数
ans+=dis[*[i-1]][*[i]];
}
printf("%d",ans);
return 0;
}
广告：
队长：一株寒冰射手
快来加入吧！
这里空空如也
有帮助，赞一个