| 算法 | 限制 | 时间复杂度 |
| Dijkstra | 无法处理负权边 | O(n2) |
| Dijkstra_Heap | 无法处理负权边 | O(mlogn) |
| Bellman_Ford | 可处理负权边，时间成本太高 | O(nm) |
| SPFA | 可处理负权边 | O(km)，特殊情况下可能退化成O(nm) |
建立一个虚拟源点，从虚拟源点向各个起始点连一条权值为0的边。
则原问题等价于从虚拟源点到终点的最短路径长度。
如此便成功将一个多源最短路问题转化为了一个单源最短路问题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e3+10,M=2e4+10;
struct Edge{
int to,next,w;
}edge[M+N<<1];int idx;
int h[N];
int dis[N],vis[N];
int n,m,s,t;
void add_edge(int u,int v,int w){edge[++idx]={v,h[u],w};h[u]=idx;}
void dijkstra()
{
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
priority_queue<pair<int,int> > q;
dis[0]=0;
q.push(make_pair(0,0));
while(!q.empty())
{
int k=q.top().second;
q.pop();
if(vis[k])continue;
vis[k]=1;
for(int i=h[k];~i;i=edge[i].next)
{
int to=edge[i].to,w=edge[i].w;
if(dis[to]>dis[k]+w)
{
dis[to]=dis[k]+w;
q.push(make_pair(-dis[to],to));
}
}
}
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&t))
{
memset(h,-1,sizeof h);
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
}
scanf("%d",&s);
for(int i=1;i<=s;i++)
{
int x;scanf("%d",&x);
add_edge(0,x,0);
}
dijkstra();
if(dis[t]==0x3f3f3f3f)printf("-1\n");
else printf("%d\n",dis[t]);
}
return 0;
}
分层图实际上是借助动态规划的思想考虑最短路问题，而后再用求最短路的算法来解决的一种思想。
考虑在每层的图上各点间连原有的边，在相邻层之间连权值为0的边。
而后原问题就转化为从第一层图的起点走到最后一层图的终点的最短路问题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e4+10,M=5e4+10,MAXK=11;
struct Edge{
int to,next,w;
}edge[M*MAXK*4]; int idx;
int h[N*MAXK];
int dis[N*MAXK],vis[N*MAXK];
int n,m,K,s,t;
void add_edge(int u,int v,int w){edge[++idx]={v,h[u],w};h[u]=idx;}
void dijkstra(int s)
{
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
priority_queue<pair<int,int> > q;
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
int k=q.top().second;
q.pop();
if(vis[k])continue;
vis[k]=1;
for(int i=h[k];~i;i=edge[i].next)
{
int to=edge[i].to,w=edge[i].w;
if(dis[to]>dis[k]+w)
{
dis[to]=dis[k]+w;
q.push(make_pair(-dis[to],to));
}
}
}
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d%d",&n,&m,&K);
scanf("%d%d",&s,&t);
while(m--)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
for(int i=0;i<=K;i++)
{
add_edge(u+i*n,v+i*n,w);
add_edge(v+i*n,u+i*n,w);
}
for(int i=0;i<K;i++)
{
add_edge(u+i*n,v+(i+1)*n,0);
add_edge(v+i*n,u+(i+1)*n,0);
}
}
for(int i=0;i<K;i++)add_edge(t+i*n,t+(i+1)*n,0);
dijkstra(s);
printf("%d\n",dis[t+K*n]);
}
题目链接
在Dijkstra原算法上稍作修改。
每次松驰操作更新最短路时，同时更新计数数组。
若更新不成功，转而判断当前路径是否与当前最短路长度相等，若是则累加计数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e6+10,M=2e6+10,mod=1e5+3;
struct Edge{
int to,next,w;
}edge[M<<1]; int idx;
int h[N];
int dis[N],vis[N],cnt[N];
int n,m;
void add(int u,int v,int w){edge[++idx]={v,h[u],w};h[u]=idx;}
void dijkstra(int s)
{
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
priority_queue<pair<int,int> > q;
dis[s]=0,cnt[s]=1;
q.push(make_pair(0,s));
while(!q.empty())
{
int k=q.top().second;
q.pop();
if(vis[k])continue;
vis[k]=1;
for(int i=h[k];~i;i=edge[i].next)
{
int to=edge[i].to,w=edge[i].w;
if(dis[to]>dis[k]+w)
{
dis[to]=dis[k]+w;
cnt[to]=cnt[k];
q.push(make_pair(-dis[to],to));
}
else if(dis[to]==dis[k]+w)
{
(cnt[to]+=cnt[k])%=mod;
}
}
}
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v,1);
add(v,u,1);
}
dijkstra(1);
for(int i=1;i<=n;i++)printf("%d\n",cnt[i]);
return 0;
}
题目链接
原文：https://www.cnblogs.com/ninedream/p/13393297.html