我的位置:首页 > 综合>其它

最短路径(随便写写)(Floyd,Bellman-Ford,Dijkstra)

时间:2020-03-24 22:17:00 来源:互联网 作者: 神秘的大神 字体:

3种常用的最短路径算法

最初学的算法之一,(之3),好怀念啊

 

#include<bits/stdc++.h>
using namespace std; int n,m,p; int dis[1000],f[1000][1000],k,ans,minn=1e9,v,b,w; bool t[1000]; void input1() { cin>>n>>m>>p; memset(dis,0x7f,sizeof(dis)); memset(f,0x7f,sizeof(f)); memset(t,0,sizeof(t)); dis[p]=0; t[p]=true; for(int i=1;i<=m;i++) { cin>>v>>b>>w; f[i][i]=0; f[v][b]=f[b][v]=w; } for(int i=1;i<=n;i++) dis[i]=min(dis[i],f[p][i]); } void dijkstra() { for(int i=1;i<=n-1;i++) { minn=1e9; k=0; for(int i=1;i<=n;i++) { if(!t[i]&&dis[i]<minn) { minn=dis[i]; k=i; } } if(k==0) break; t[k]=true; for(int i=1;i<=n;i++) if(i!=k) dis[i]=min(dis[i],dis[k]+f[k][i]); } for(int i=1;i<=n;i++) cout<<i<<' '<<':'<<' '<<dis[i]<<endl; } void text1_dijkstra() { input1(); dijkstra(); } struct ed { int from; int next; int weight; } edge[1000]; void input2() { cin>>n>>m>>p; memset(dis,0x7f,sizeof(dis)); dis[p]=0; for(int i=1;i<=m;i++) { cin>>edge[i].from>>edge[i].next>>edge[i].weight; if(edge[i].from==p) dis[edge[i].next]=edge[i].weight; } } void relax(int u1,int v1,int w1) { if(dis[v1]>dis[u1]+w1) dis[v1]=dis[u1]+w1; } int bellman_ford() { for(int i=1;i<=n-1;i++) for(int j=1;j<=m;j++) relax(edge[j].from,edge[j].next,edge[j].weight); bool fool=false; for(int i=1;i<=m;i++) if(dis[edge[i].from]>dis[edge[i].next]+edge[i].weight) { fool=true; break; } if(!fool) for(int i=1;i<=n;i++) cout<<i<<' '<<':'<<' '<<dis[i]<<endl; } void text2_bellman_ford() { input2(); bellman_ford(); } void input3() { cin>>n>>m>>p; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=1e8; for(int i=1;i<=m;i++) { cin>>v>>b>>w; f[i][i]=0; f[v][b]=f[b][v]=w; } } void floyd() { for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=k&&i!=j&&j!=k) f[i][j]=min(f[i][k]+f[k][j],f[i][j]); } } } for(int i=1;i<=n;i++) if(i!=p) cout<<i<<' '<<':'<<' '<<f[p][i]<<endl; } void text3_floyd() { input3(); floyd(); } int main() { //text1_dijkstra();//迪杰斯特拉算法 //text2_bellman_ford();//贝尔曼-福特算法 //text3_floyd();//弗洛伊德算法
    return 0; }

 

ps(这里的Bellman-Ford是处理有向图的,处理无向图只需将input2的循环里加上if(edge[i].next==p) dis[edge[i].from]=edge[i].weight;)

虽然还有许多其他算法,比如说SPFA,但某蒟蒻就不写了,懒。。。