最短路径模板(dijkstra,floyed)

发布于:2021-11-30 17:11:58

n个点,m条边,给定起点和终点,求单源最短路径。


(一)dijkstra算法:单源最短路径

#include
#define inf 0x3f3f3f3f
#define maxn 100
#define sf scanf
#define pf printf
using namespace std;
int n,m,x,y,z; //n个城市和m条道路
int mp[maxn][maxn],lowcost[maxn],vis[maxn],pre[maxn];
void dijkstra(int sta,int edd){
for(int i=0;i vis[sta]=1; lowcost[sta]=0;
//寻找距离原点最小的点加进集合 (除原点)
for(int i=1;i int Min=inf;
int v=-1;
for(int j=0;j if(!vis[j]&&lowcost[j] Min=lowcost[j];
v=j;
}
}

//如果又一次更新失败退出此次循环
if(Min==inf) {
break;
}
vis[v]=1;
//用新加进来的点松弛
for(int k=0;k if(!vis[k]&&lowcost[v]+mp[v][k] lowcost[k]=lowcost[v]+mp[v][k];
pre[k]=v;
}
}
}
}

int main(){
sf("%d%d",&n,&m);
for(int i=0;i for(int j=0;j mp[i][j]=inf;
}
mp[i][i]=0;
}
for(int i=0;i sf("%d%d%d",&x,&y,&z);
mp[x][y]=mp[y][x]=z;
}
dijkstra(0,n-1);

if(lowcost[n-1]==inf ) cout<<"-1"< else cout<
//假设打印起点是0,终点是n-1的路径
int sta=0,ed=n-1;
pre[sta]=-1;
vector ve;
vector::iterator ite;
while(pre[ed]!=-1){
ve.push_back(ed);
ed=pre[ed];
}
reverse(ve.begin(),ve.end());
cout< for(ite=ve.begin();ite!=ve.end();++ite){
cout<<*ite;
if(ite!=ve.end()) cout<<" ";
else cout< }
return 0;
}

(二)floyed:多源最短路径

#include
#define inf 0x3f3f3f3f
#define maxn 100
#define sf scanf
#define pf printf
using namespace std;
int n,m,x,y,z; //n个城市和m条道路
int mp[maxn][maxn],lowcost[maxn],vis[maxn],pre[maxn],flag=false;

//k是中间结点,i是起点,j是终点
void floyed(int mp[][maxn]){
for(int k=0;k for(int i=0;i for(int j=0;j if(mp[i][j]>mp[i][k]+mp[k][j]){
mp[i][j]=mp[i][k]+mp[k][j];
}
}
}
}
}
int main(){
sf("%d%d",&n,&m);
for(int i=0;i for(int j=0;j mp[i][j]=inf;
}
mp[i][i]=0;
}
for(int i=0;i sf("%d%d%d",&x,&y,&z);
mp[x][y]=mp[y][x]=z;
}
floyed(mp);
//可以判断是否存在负环
for(int i=0;i if(mp[i][i]<0){
flag=true;
}
}
if(flag) cout<<"存在负环"< else cout<<"不存在负环"<// cout< return 0;
}

相关推荐

最新更新

猜你喜欢