【图论】关于Dijkstra与Spfa算法区别的思考和分析
Dijkstra与Spfa算法区别的思考和分析
一、前言
在最短路问题中，Dijkstra算法与Spfa算法都是比较常用的算法。但是如果学习了这两个算法我们就能发现Dijkstra算法的优先队列优化与Spfa算法的代码极为相似，如果不去深入了解两个算法的原理与区别的话在写代码的时候很容易混淆。因此笔者希望通过写下这篇博客来分析一下两者之间的区别。
相关博客链接：
Dijkstra算法介绍
Spfa算法介绍
二、算法原理区别分析
重难点：bool数组ch[N]的使用与if语句判断位置
最大区别：SPFA算法可以处理带负权的边，而Dijkstra算法不行。
两个算法代码相似的原因是都使用到了队列数据结构，但是两个算法的原理差别其实还是不小的。在这里先简单复习一下两个算法
- Dijkstra： 首先存下每条边的长度与连接的端点与初始化每两个点之间的距离为正无限大。然后通过循环，每一次循环确定一个点i，i点是目前所有未确定点中距离起点最近的点，然后枚举所有未确定的点j，看看是从之前的已经确定的点到j点的距离近还是从i点到j点的距离近。
- Spfa： 在Bellman_Ford算法中，我们需要依次遍历每一条边（a----->b，长为w）来更新我们的dis[b]。但是我们发现，如果dis[a]在循环中如果一直没有出现变化，那么公式（dis[b]=min(dis[b],te[a]+w)）就一直不会更新我们的dis[b]，做了很多的无用操作，对程序的运行速度造成了比较大的影响。那我们需要这样去想：我们可不可以用一个方法记录一下a的状态，只有当dis[a]发生了变化时，我们才去更新所有以a为起点的点呢？这，就是Spfa算法的思路。而在时间复杂度上，虽然spfa算法的时间复杂度有退化的可能性，但基本上优于Bellman_Ford。
1.Dijkstra分析
通过阅读算法原理，在Dijkstra算法中，我们重点维护的对象是距离起点最近的点。通过每一次循环来每次确定一个距离起点最近的点，然后用这个点去更新所有未确定的点。每次确定一个点我们都要做好标记让它不再被更新。由于图中可能出现环，所以已经被确定的点也有可能被push进我们的优先队列中，因此：当我们每次从优先队列中取出元素后，需要判断一下该点是否已经被确定，如果已经被确定，我们当然不能用它来更新其它点，因此把它continue掉。
核心代码：
mem(ch, 0);
mem(dis, 0x3f);
priority_queue<pii ,vector<pii>,greater<pii>>q;
dis[k] = 0;
q.push({ 0,k });
while (!q.empty())
{
auto te = q.top();
q.pop();
int d = te.first,idt=te.second;
if (ch[idt])continue; //dijkstra算法中一旦一个点被确定后就不能再被遍历，因此在遍历所连接的边前就要判断
ch[idt] = true;
for (int i = h[idt]; ~i; i = ne[i])
{
int j = e[i];
if (dis[j] > d + w[i])
{
dis[j] = d + w[i];
q.push({ dis[j],j });
}
}
}
2.Spfa分析
和Dijkstra算法不同的是，Spfa算法相比与点，它所维护的重点是与点相连接的边。也就是说虽然是用队列来储存点，但是算法的重点还是在取出点后遍历点的所有边，而边的遍历在Spfa算法中可能不止一次。这就导致了一点：在Dijkstra算法中，bool数组ch[N]只能修改一次，但是Spfa算法却允许ch[N]被反复修改，原因如下：
在Dijkstra算法中，ch数组所记录的是已经被确定的点，确定的点是不能回归到不确定的状态的，因此当然不能被修改ch数组。
而在Spfa算法中，ch数组所记录的是距离被更新过的点，它的定义就决定了ch数组是可以被多次修改的，原因是一个点的dis可以被多次修改。如果一个点已经在队列中等待用来更新其它的距离了，那么我们就没有再让一个点入队的必要了。
核心代码：
mem(ch, 0);
mem(dis, 0x3f);
queue<int>q;
dis[k] = 0;
ch[k] = true;
q.push(k);
while (!q.empty())
{
int te = q.front();
q.pop();
ch[te] = false;
for (int i = h[te]; ~i; i = ne[i])
{
int j = e[i];
if (dis[j] > dis[te] + w[i]) //即使一个点已经被更新了在队列中也要比较
{
dis[j] = dis[te] + w[i]; //因为dis可能比上一次更新时更短了
if (!ch[j]) //在spfa算法中，ch数组判断的是目标点是否在队列中避免同一点反复入队即使不入队也可以更新因此只在入队前查重
{
q.push(j);
ch[j] = true;
}
}
}
}
三、例题讲解分析
1.例题引入
链接：Acwing 香甜的黄油
农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。
把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。
当然，他将付出额外的费用在奶牛上。
农夫John很狡猾，就像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。
他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。
给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。
数据保证至少存在一个牧场和所有牛所在的牧场连通。
输入格式
第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。
第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。
第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场A、B，两牧场间距 D，当然，连接是双向的。
输出格式
共一行，输出奶牛必须行走的最小的距离和。
数据范围
1≤N≤500,
2≤P≤800,
1≤C≤1450,
1≤D≤255
输入样例：
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例：
8
2.题目分析
任意两点距离，第一反应就是Floyd算法，但是仔细一想，O(n3)的时间复杂度让Floyd算法并不适合解决本题。因此我们换个思路，思考其它的解题思路，然后我们发现做n次优先队列优化后的Dijkstra算法（O(nmlogn)）和Spfa（O(nnm)）的时间复杂度都是够的。
3.正确代码
这里两种代码都给出来，都是可以过的。
//#pragma gcc optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define int long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int, int> pii;
const int N = 1e6 + 7;
int n, p, c;
int cow[1550];
int h[1550], e[3500], ne[3500], w[3500], id = 1;
bool ch[1550];
int dis[1250];
void add(int a, int b, int c)
{
ne[id] = h[a];
h[a] = id;
e[id] = b;
w[id] = c;
id++;
}
int dijkstra()
{
int ans = inf;
for (int k = 1; k <= p; k++)
{
mem(ch, 0);
mem(dis, 0x3f);
priority_queue<pii ,vector<pii>,greater<pii>>q;
dis[k] = 0;
q.push({ 0,k });
while (!q.empty())
{
auto te = q.top();
q.pop();
int d = te.first,idt=te.second;
if (ch[idt])continue; //dijkstra算法中一旦一个点被确定后就不能再被遍历，因此在遍历所连接的边前就要判断
ch[idt] = true;
for (int i = h[idt]; ~i; i = ne[i])
{
int j = e[i];
if (dis[j] > d + w[i])
{
dis[j] = d + w[i];
q.push({ dis[j],j });
}
}
}
int res = 0;
for (int i = 1; i <= n; i++)
if(dis[cow[i]]<inf)
res += dis[cow[i]];
else
{
res = inf;
break;
}
if(res<inf)
ans = min(ans, res);
}
return ans;
}
int spfa()
{
int ans = inf;
for (int k = 1; k <= p; k++)
{
mem(ch, 0);
mem(dis, 0x3f);
queue<int>q;
dis[k] = 0;
ch[k] = true;
q.push(k);
while (!q.empty())
{
int te = q.front();
q.pop();
ch[te] = false;
for (int i = h[te]; ~i; i = ne[i])
{
int j = e[i];
if (dis[j] > dis[te] + w[i])
{
dis[j] = dis[te] + w[i];
if (!ch[j]) //在spfa算法中，ch数组判断的是目标点是否在队列中避免同一点反复入队即使不入队也可以更新因此只在入队前查重
{
q.push(j);
ch[j] = true;
}
}
}
}
int res = 0;
for (int i = 1; i <= n; i++)
if (dis[cow[i]] < inf)
res += dis[cow[i]];
else
{
res = inf;
break;
}
if (res < inf)
ans = min(ans, res);
}
return ans;
}
void solve()
{
mem(h, -1);
cin >> n >> p >> c;
for (int i = 1; i <= n; i++)
cin >> cow[i];
for (int i = 1; i <= c; i++)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
add(y, x, z);
}
cout << spfa() << endl;
//cout << dijkstra() << endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
作者：Avalon Demerzel，喜欢我的博客就点个赞吧，更多图论与数据结构知识点请见作者专栏《图论与数据结构》
上一篇： 关于CSS flex布局学习笔记整理
下一篇： 图论-SPFA算法