一、Floyd
int n; void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(maps[i][j]>maps[i][k]+maps[k][j]){ maps[i][j]=maps[i][k]+maps[k][j]; } } } } }二、Dijkstra
#define INF 0x3f3f3f3f int n,m; int dis[M]; int vis[M]; int maps[M][M]; void init(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ maps[i][j]=INF; } maps[i][i]=0; } memset(vis,0,sizeof(vis)); } void dijkstra(int s){ for(int i=1;i<=n;i++) dis[i]=INF; dis[s]=0; for(int i=1;i<=n;i++) dis[i]=maps[s][i]; for(int i=1;i<=n;i++){ int Min=INF,k; for(int j=1;j<=n;j++){ if(!vis[j]&&Min>dis[j]) Min=dis[j],k=j; } vis[k]=1; for(int j=1;j<=n;j++){ if(!vis[j]&&dis[j]>maps[k][j]+dis[k]) dis[j]=maps[k][j]+dis[k]; } } } //dijkstra(1) 指的是选定1为源点 //cout<<dis[n] 指的是输出 1 到 n 的最短距离三、Bellman_ford
#define M 105 #define INF 0x3f3f3f3f struct node{ int u,v,w; }edge[M]; int dis[M]; int n,m,s; void init(){ cin>>n>>m>>s; for(int i=1;i<=n;i++){ dis[i]=INF; } dis[s]=0; for(int i=1;i<=m;i++){ cin>>edge[i].u>>edge[i].v>>edge[i].w; if(edge[i].u==s){ dis[edge[i].v]=edge[i].w; } } } bool bellmanford(){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w){ dis[edge[j].v]=dis[edge[j].u]+edge[j].w; } } } int flag=1; for(int i=1;i<=m;i++){ if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w){ flag=0; break; } } return flag; } //nodenum 节点数 //edgenum 边数 //source 源点 //distance 距离本来想细细地写一下思路，就简单说一下吧。 迪杰斯特拉和贝尔曼的区别就是一个用点找最短路，一个用边找最短路，单源点，选定之后先找出此点直接相连的各个点的边权，然后进行比较，为啥是双循环，因为一次松弛一下，全来一遍准确，还有spfa，之后补上。 写的都是板子，这两天刚开始学，说错的写错的之后再改吧。
