Floyd算法
要点分析
- Floyd算法的核心思想是动态规划,对于i、j的距离,使用第k个点进行优化。
- DP状态 d p k , i , j dp_{k,i,j} dpk,i,j为当中间点仅从1…k选取时i和j的最短路径
- DP转移为 d p k , i , j = m i n { d p k − 1 , i , j , d p k − 1 , i , k + d p k − 1 , k , j } dp_{k,i,j}=min\{dp_{k-1,i,j},dp_{k-1,i,k}+dp_{k-1,k,j}\} dpk,i,j=min{dpk−1,i,j,dpk−1,i,k+dpk−1,k,j}
- 对对一维加上滚动数组的优化,就成了熟知的Floyd。
实现代码
int graph[N][N];
for(int k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(graph[i][j]>graph[i][k]+graph[k][j])
graph[i][j]=graph[i][k]+graph[k][j]
Dijkstra算法
要点分析
- Dijkstra算法的核心思想是贪心,算法认为在每轮优化后与源点距离最短的一点被最终确定,可以通过这一点来松弛优化其他点。
- 当边权都为正数时,以上思想没有错。但是当有负权边时,这种确定性不再存在,因为后续可能通过负边有更短的距离。这就是Dijkstra算法不能处理负权边的原因。
如图,初始时依据Dijkstra算法便可确定B距源点A的最短距离为4,但事实上最短距离为A-C-B(5-3=2)。
实现代码
struct Vec
{
int v,d;
Vec(){}
Vec(int _v,int _d):v(_v),d(_d){}
friend bool operator<(const Vec & a,const Vec & b){return a.d>b.d;}
}
const int N=1e3+10,M=1e4+10,INF=0x3f3f3f3f;
int n,m,s;//s为源点
int idx=2,first[N],nxt[M],to[M],val[M];//链式前向星
int dist[N];
void dijkstra()
{
priority_queue<Vex> q;
memset(dis, INF, sizeof(dis));
dis[id[s]] = 0;
q.push(Vex(id[s], 0));
while(!q.empty())
{
Vex cur = q.top(); q.pop();
int u = cur.v, d = cur.d;
if(d != dis[u])//相当于vis[u]判别
continue;
for(int p = first[u]; p; p = nxt[p])
{
int v = to[p], w = val[p];
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
q.push(Vex(v, dis[v]));
}
}
}
}
Bellman-Ford算法
要点分析
- 第k轮循环的含义是:从源点s最多经过k条边到达其余各点的最短路径长度。
- 总共优化n-1轮即可,因为在包含n个顶点的图中,任意两点的最短路径不可能包含回路,即最短路径总是一条简单路径,路径上最多串连n个点,所以最多有n-1条边。
- 证明:最短路径不可能包含回路。
- 当回路为正环(回路权值和为正)时,去掉回路会带来更短。
- 当回路为负环时,没走一圈负环,路径长度都会减少,所以此时最短距离为 − ∞ - \infty −∞,即不存在最短路径。
- 鉴于以上原因,当n-1轮循环结束后,如果发现仍能更新缩短最短距离,表明图中有负环。
实现代码
int u[M],v[M],w[M];//边集
//Bellman-Ford
for(int k=1;k<=n-1;k++)
for(int i=1;i<=m;i++)
if(dist[v[i]]>dist[u[i]]+w[i])
dist[v[i]]=dist[u[i]]+w[i];
//判断负环
for(int i=1;i<=m;i++)
if(dist[v[i]]>dist[u[i]]+w[i])
printf("Negtive Round!\n"),break;
SPFA算法
要点分析
- Bellman-Ford算法存在一些冗余,即有些点可能用不着n-1轮循环就能找到最短路径。如果此轮dist[v]未得到过更新,则表明dist[v]已经是最小值。否则,dist[v]还可能再次得到更新。
- 鉴于1中的分析,我们利用队列只记录具有更新潜力的点,只更新这些点。
- 另外,一个点在队列中存在多个没有意义,所以我们用inq[]确保唯一。
- 与Bellman-ford的负环判断原理相同,一个点至多被更新n-1次,否则说明图中有负环。
实现代码
const int N=1e3+10,M=1e4+10,INF=0x3f3f3f3f;
int n,m,s;//s为源点
int idx=2,first[N],nxt[M],to[M],val[M];//链式前向星
queue<int> q;//spfa
bool inq[N];//spfa
int dist[N];//spfa
int pre[N]//spfa(可选-追溯路径)
void addE(int u,int v,int w)
{
to[idx]=v,val[idx]=w;
nxt[idx]=first[u],first[u]=idx++;
}
void spfa()
{
memset(dist,INF,sizeof(dist));
memset(pre,0,sizeof(pre);
q.push(s),inq[s]=true,dist[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();inq[u]=false;
for(int p=first[u];p;p=nxt[p])
{
int v=to[p],w=val[p];
if(dist[v]>dist[u]+w)
{
dist[v]=dist[u]+w;
pre[v]=p;//记录链式前向星索引更方便
if(!inq[v])
q.push(v),inq[v]=true;
}
}
}
}
对各种算法的比较
. | Floyd | Dijistra | Bellman-Ford | SPFA |
---|---|---|---|---|
时间复杂度 | O(N^3) | O((N+M)logn) | O(NM) | 最坏O(NM) |
空间复杂度 | O(N^2) | O(M) | O(M) | O(M) |
是否可以处理负权边 | YES | NO | YES | YES |
是否可以处理负环 | NO | NO | YES | YES |
实现效果 | 多源 | 单源 | 单源 | 单源 |
- Floyd算法代码简单,用于含有负权边的情况下直接得出所有点之间的最短距离。
- Dijkstra算法在求单源最短距离时效率最高,较为常用,但是无法处理负权边。
- 对于Bellman-Ford和SPFA,后者是前者的一种优化,实现简单,可以处理负权边和检测负环,但容易被卡数据,故用于在有负权边的情况下求单源最短距离。