图论——涵盖Bellman-Ford和Dijkstra的Johnson算法(多源最短路径问题)
以Floyd作为引入
在解决单源最短路径时,我们一共有两种常用的方法Bellman-Ford和Dijkstra,前者基于动态规划,而后者基于贪心。在时间复杂度方面,前者为,后者使用优先队列,有望降为.
当然,对于所有节点对之间的最短路径计算(多源最短路径问题),也同样有两种常用方法。同样的,一种基于动态规划,另一种以贪心为主。
单源最短路径 向 多源最短路径 的过渡
很容易想到,单源最短路径问题可以看做多源最短路径的其中一个子集,处理多源最短路径可以对所有的点走一次单源最短路径,Floyd算法就是这样的思路。
Floyd思路
Floyd基于区间动态规划解决最短路问题,在实际应用中,代码复杂度要比同样是基于动态规划的Bellman-Ford简单得多,同时具有后者处理负权边的能力。并且,使用邻接矩阵实现边权值的存储,使得Floyd的时间复杂度极其稳定。
对于每两个节点和之间的路径,我们枚举它们之间经过的节点,每次比较经过和不经过的两种情况,更新和之间的最短路径。在邻接矩阵下,枚举起点、终点、间断点,时间复杂度恰好为
状态转移方程:.
(博主之前已经整理过Floyd算法,本文不做细致模拟,可以参考以前的文章图论简笔(下)——最小生成树、最短路径问题)
Code
#include<iostream>
using namespace std;
const int inf=999999;
int mp[102][102];
int dis[102][102];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=inf;
for(int i=1;i<=n;++i)
dis[i][i]=0;
for(int i=1;i<=m;++i)
{
int fr,to,w;
cin>>fr>>to>>w;
dis[fr][to]=w;
}
//Floyd算法的内核,简单的三重循环
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
printf("\n");
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
if(dis[i][j]!=inf)
printf("%5d",dis[i][j]);
else
printf(" INF");
printf("\n");
}
return 0;
}
多源最短路径的贪心方法
优先队列的Dijkstra不论是在期望复杂度,还是稳定性方面都比Bellman-Ford或者SPFA更具优越性。但是用贪心实现的Dijkstra无法处理负权边,一旦出现负权边,Dijkstra很有可能GG。我们可以从Dijkstra算法的思路上看出这一点。
Dijkstra算法的思路:
用每一次已确定最短路径的点更新其它节点,当没有节点被更新时,说明所有点到源点的最短路径已被确定。首先,从源点开始更新它所能连到的结点,假设连接的边是源点所有边中最短的,那么这条路径一定是到达的最短路径,因为其它从源点出发且经过中转到达的路径一定一开始就大于最短路径了。同理,接下来以为中转,继续更新其它结点。
那么为什么不能处理负权边,假设,我们已经规定了已经找到最短路径,在后续松弛中,又有一个结点,它有一条负权边连向,于是又被更新了,再次成为当前的最短路径结点,之后我们有找到了…这个循环就走不出了。所以可以说,Dijkstra在一些情况下处理不了负权边。
仅仅用Dijkstra构成每个结点对之间的最短路,同样也只能处理非负权边。
Johnson算法中对边的重赋值
为了获得较高的效率和稳定性,较好的选择仍然是用Dijkstra算法构成多源最短路径问题算法的一部分。目前的问题在于如何处理负权边。Johnson算法中提出了一种对边进行重新赋值的方法。
假设有一个新的点,它指向其它所有点的边的权值都为0,计算这个新的点到其它所有点的最短路径数组,把它作为边的映射关系。对于一条指向的边,其权值修改为,对所有边进行重赋值以后,在进行次Dijkstra解决个单源最短路问题。
修改后各边权值非负的证明:假设G(V,E)中存在负权边,由于新增点n+1到各个结点边的权值都为0,所以n+1到达其它所有点的最短路要么是0,要么是个负数。 设两个点和,新增点到点和点的最短路径分别文和,这两点之间边的权重为,那么满足不等式,移项后得出,新的权重必定为非负数。
最终得到答案的正确性:
设到的最短路径经历了这些点,
那么这些边的累计和,
原来的最短路即为.
用C++实现的代码模板
#include<iostream>
#include<queue>
#include<cstdio>
#include<vector>
#include<utility>
using namespace std;
const int inf=0xffffff;
typedef pair<int,int> pii;
vector<pii> edge[102];
int dis[102][102];
int mapping[102];
int n,m;
void SPFA()
{
queue<int> q;
bool vis[102];
for(int i=1;i<=n;++i)
{
mapping[i]=inf;
vis[i]=false;
}
mapping[n+1]=false;
q.push(n+1);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<edge[u].size();++i)
{
int v=edge[u][i].first;
int w=edge[u][i].second;
if(mapping[v]>mapping[u]+w)
{
mapping[v]=mapping[u]+w;
if(!vis[v])
{
vis[v]=true;
q.push(v);
}
}
}
}
}
void Dijkstra(int st)
{
priority_queue<pii> q;
for(int i=1;i<=n;++i)
dis[st][i]=inf;
dis[st][st]=0;
q.push(make_pair(0,st));
while(!q.empty())
{
pii u=q.top();
q.pop();
if(dis[st][u.second]<u.first) continue;
for(int i=0;i<edge[u.second].size();++i)
{
int v=edge[u.second][i].first;
int w=edge[u.second][i].second;
if(dis[st][v]>dis[st][u.second]+w)
{
dis[st][v]=dis[st][u.second]+w;
q.push(make_pair(dis[st][v],v));
}
}
}
}
void johnson()
{
SPFA();
for(int i=1;i<=n;++i)
for(int j=0;j<edge[i].size();++j)
edge[i][j].second+=mapping[i]-mapping[edge[i][j].first];
for(int i=1;i<=n;++i)
Dijkstra(i);
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
edge[n+1].push_back(make_pair(i,0));
for(int i=1;i<=m;++i)
{
int fr,to,w;
scanf("%d %d %d",&fr,&to,&w);
edge[fr].push_back(make_pair(to,w));
}
johnson();
printf("\n");
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
if(dis[i][j]!=inf)
printf("%5d",dis[i][j]+mapping[j]-mapping[i]);
else
printf(" INF");
printf("\n");
}
return 0;
}