PS：能求带负边图，但不能带负权回路 可以求出任意两点之间的最短路径 主代码：
for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j&&j!=k&&i!=k) dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);PS:不支持负边 求单源最短路径，即起点只有一个 主代码：
#include<iostream> #include<cstring> #define maxn 9999999 using namespace std; int f[101][101]; int n,m,x,y,s; int pre[101];//记录前驱 int to[101];//从起点到当前节点的距离 int v[101];//是否访问过 int main() { cin>>n>>m; memset(f,maxn,sizeof(f)); for(int i=1;i<=m;i++) { cin>>x>>y>>s; f[x][y]=f[y][x]=s; } for(int i=2;i<=n;i++) { to[i]=f[1][i];//从第一个点到每个点的初始距离 if(f[1][i]!=maxn)//如果被修改前驱就是第一个点 pre[i]=1; } v[1]=1; for(int i=2;i<=n;i++) { int minn=maxn; int k=0; for(int j=2;j<=n;j++) if(v[i]==0&&to[i]<minn)//如果没被标记过且小于最小值就替换 { minn=to[i]; k=j; } v[k]=1;//找到了当前最短路 for(int j=1;j<=n;j++) if(to[k]+f[k][j]<to[j])//从当前最短路找下一条最短路 to[j]=to[k]+f[k][j]; } }用(循环)队列优化的Bellman-FordPS:支持负边，但不支持负环回路（如果回路只走一次就行）
team[]为队列 exist[]为一个点是否在队列中 dis[i]记录从起点到i的最短距离 w[i][j]表示从i到j的长度 pre[]前驱 do { head++; exist[u]=0; for枚举所有链接的点 if(dis[v]>dis[u]+w[u][v]) { dis[v]=dis[u]+w[u][v]; pre[v]=u; if(exist[v]==0) { exist[v]=1; tail++; team[tail]=v; } } } while(head<tail)一个例题加深理解 例题：洛谷P3371单源最短路径模板https://www.luogu.org/problemnew/show/P3371 此处运用SPFA+链式前向星
#include<iostream> using namespace std; int exist[500010]; int team[2000000]; int dis[500010]; int head[500010]; int n,m,s; int x,y,z; int cnt; int t=0,w=1; struct edge { int next; int to; int w; }edge[2500010]; void add(int u,int v,int w) { edge[++cnt].w=w; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; } int main() { cin>>n>>m>>s; for(int i=1;i<=n;i++) dis[i]=2147483647; for(int i=1;i<=m;i++) { cin>>x>>y>>z; add(x,y,z); } dis[s]=0; team[1]=s; while(t<w) { t++; int u=team[t];//u等于入队的点 exist[u]=0; for(int i=head[u];i!=0;i=edge[i].next)//i从每个点能到的最后一条遍循环到第一条边 { int v=edge[i].to;//v等于每条遍的后面那个点 if(dis[v]>dis[u]+edge[i].w)//如果到这条遍后面的点距离比到这条边前面点加上边的权值小 { dis[v]=dis[u]+edge[i].w; if(!exist[v]) { w++; exist[v]=1; team[w]=v; } } } } for(int i=1;i<=n;i++) cout<<dis[i]<<" "; }转载于:https://www.cnblogs.com/BrokenString/p/9279536.html
相关资源：GA遗传算法最短路径万能通用matlab代码