单源最短路
SPFA
队列优化 Bellman-Ford 算法 。
关于 SPFA ，他死了 。
时间复杂度 \(O(nm)\) （容易被卡，不太稳定）
如何判断负环：
用 SPFA ，设 \(cnt[i]\) 表示 \(1\) 到 \(i\) 的最短路条数。松弛一条边的时候用 \(cnt[u]+1\) 来更新 \(cnt[v]\) ，若 \(cnt[v]\ge n\) 则说明出现了负环 。
证明：\(1\) 到 \(i\) 的最短路最多只有 \(n-1\) 条，若 \(cnt\ge n\) ，则一个点必然经过了至少 \(2\) 次，则出现了负环 。
P3385 【模板】负环 核心代码：
#define Maxn 2005
#define Maxm 3005
void spfa()
{
memset(inq,false,sizeof(inq)),memset(cnt,0,sizeof(cnt)),memset(ds,inf,sizeof(ds)),ds[1]=0;
queue<int> q; q.push(1),inq[1]=true;
while(!q.empty() && !exfu) // 这里一定要判断，不然会死循环
{
int cur=q.front(); q.pop(),inq[cur]=false;
for(int i=hea[cur];i;i=nex[i]) if(ds[ver[i]]>ds[cur]+edg[i])
{
ds[ver[i]]=ds[cur]+edg[i],cnt[ver[i]]=cnt[cur]+1;
if(cnt[ver[i]]>=n) exfu=true; // 要特别注意整个图有多少个点
else if(!inq[ver[i]]) q.push(ver[i]),inq[ver[i]]=true;
}
}
}
spfa(),printf(exfu?"YES\n":"NO\n");
Dijkstra
只适合处理没有负环的图 。
加上 系统堆 优化后，时间复杂度为 \(O((n+m)\log m)\) （没错，就是 \(m\) ，因为 priority_queue<> 中会有一大堆重复的元素，从而导致堆中最多可能有 \(m\) 个元素）。
但是如果只用 堆 ,复杂度仍然是 \(O((n+m)\log n)\) ，因为堆的信息会及时更新，剔除重复元素。
当然，如斐波那契堆的复杂度可以进一步优化到 \(O(n\log n+m)\)
\(\rightarrow\) 所以，每个节点最多只会增广一次。即，每个节点只会进行一次遍历儿子的操作。
一般使用的时候可以结合 SPFA 记录进队信息和队列优化 。
P4779 【模板】单源最短路径（标准版） 核心代码 ：
#define Maxn 100005
#define Maxm 500005
bool inq[Maxn];
struct Data
{
int num,val;
bool friend operator < (Data x,Data y){ return x.val>y.val; }
}cur;
void dij_spfa()
{
memset(ds,inf,sizeof(ds)),ds[s]=0,inq[s]=true;
priority_queue<Data> q;
q.push((Data){s,0});
while(!q.empty())
{
cur=q.top(),q.pop(),inq[cur.num]=false;
if(cur.val>ds[cur]) continue;
for(int i=hea[cur.num];i;i=nex[i])
if(ds[ver[i]]>ds[cur.num]+edg[i])
{
ds[ver[i]]=ds[cur.num]+edg[i];
if(!inq[ver[i]]) q.push((Data){ver[i],ds[ver[i]]}),inq[ver[i]]=true;
}
}
}
dij_spfa();
全源最短路
Floyd
用来求两个点之间的最短路，复杂度高，常数小，便于实现 。
时间复杂度：\(O(n^3)\) 。
核心代码：
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[j][k]);
Johnson
Johnson 算法通过一种方法给每条边重新标注边权，使每一条边都变为正整数，最后通过 \(n\) 轮 Dijkstra 求出全源最短路 。
-
我们新建一个虚拟节点（ 在这里我们就设它的编号为 \(0\) ）。从这个点向其他所有点连一条边权为 \(0\) 的边 。
-
接下来用 SPFA 算法求出从 \(0\) 号点到其他所有点的最短路，记为 \(h_i\) （ \([x\in [1,n]~|~h_i\le 0]\) ）。
-
假如存在一条从 \(u\) 点到 \(v\) 点，边权为 \(w\) 的边，则我们将该边的边权重新设置为 \(w+h_u-h_v\) 。
-
接下来以每个点为起点，跑 \(n\) 轮 Dijkstra 算法即可求出任意两点间的最短路了 。
具体证明详见 \(OI~Wiki\) 最短路
时间复杂度：\(O(nm\log m)\) 。
P5905 【模板】Johnson 全源最短路 核心代码：
#define Maxn 3005
#define Maxm 6005
ll ds[Maxn];
void spfa()
{
memset(h,inf,sizeof(h)),h[0]=0;
queue<int> q; q.push(0),inq[0]=true;
while(!q.empty() && !exfu)
{
int cur=q.front(); q.pop(),inq[cur]=false;
for(int i=hea[cur];i;i=nex[i]) if(h[ver[i]]>h[cur]+edg[i])
{
h[ver[i]]=h[cur]+edg[i],cnt[ver[i]]=cnt[cur]+1;
if(cnt[ver[i]]>=n+1) exfu=true; // 特别注意这里有 n+1 个点
else if(!inq[ver[i]]) inq[ver[i]]=true,q.push(ver[i]);
}
}
}
void dij(int x)
{
for(int i=1;i<=n;i++) ds[i]=infll;
memset(inq,0,sizeof(inq)),ds[x]=0;
priority_queue<Data> q;
q.push((Data){x,0}),inq[x]=true;
Data cur;
while(!q.empty())
{
cur=q.top(),q.pop(),inq[cur.num]=false;
for(int i=hea[cur.num];i;i=nex[i]) if(ds[ver[i]]>ds[cur.num]+1ll*edg[i])
{
ds[ver[i]]=ds[cur.num]+1ll*edg[i];
if(!inq[ver[i]]) inq[ver[i]]=true,q.push((Data){ver[i],ds[ver[i]]});
}
}
}
n=rd(),m=rd();
for(int i=1,u,v,d;i<=m;i++) u=rd(),v=rd(),d=rd(),add(u,v,d);
for(int i=1;i<=n;i++) add(0,i,0);
spfa();
if(exfu) printf("-1\n");
else
{
for(int i=1;i<=tot;i++) edg[i]+=h[fro[i]]-h[ver[i]];
ll MAX=1000000000ll,ans;
for(int i=1;i<=n;i++)
{
dij(i),ans=0;
for(int j=1;j<=n;j++) ans+=1ll*j*((ds[j]==infll)?MAX:(ds[j]+h[j]-h[i]));
printf("%lld\n",ans);
}
}