本文共 950 字，大约阅读时间需要 3 分钟。
floyd(){ rep(k,1,n) rep(i,1,n) { // if(a[i][k]==maxn||i==k) continue; rep(j,1,n) { a[i][j]=min(a[i][j],a[i][k]+a[k][j]); } }} 三重循环，k为枚举中间点
方便简单，n3爆时间void spfa（）｛ for(int i=1;i<=n;i++) dis[i]=inf; queue q; dis[v0]=0;q.push(v0);vis[v0]=1; while(!q.empty()) { int u=q.front();q.pop();vis[u]=0; for(int i=e[u].head;i;i=e[i].next) { int v=e[i].v,w=e[i].w; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; if(!vis[v]) ｛q.push(v);vis[v]=1；} } } }｝ 最实用的，但可能会被数据卡成n*m
靠队列更新，根据三角形定则来进行放缩；可判负环 只要判断一个点进入次数是否大于n Djstlvoid Djstl(int x){ priority_queue ,cmp> q; dis[x]=0;q.push(x); while(!q.empty()) { int u=q.top();q.pop(); if(!tag[u]) { tag[u]=1; for(int i=e[u].first;i;i=e[i].next) { int v=e[i].v,w=e[i].w; dis[v]=min(dis[v],dis[u]+w); q.push(v); } } }} 邻接矩阵 O(n^2)
邻接表 O(n^2) 邻接表+binary heap O((n+m)logn) 邻接表+fibonacci heap O(m+nlogn)转载地址：http://mfihn.baihongyu.com/