SPFA
What is SPFA
The SPFA (Shortest Path Faster Algorithm) is an optimization of the Bellman-Ford algorithm.
How does it works
When we use Bellman Ford, we find that all the edges will be relaxed at least once even it‘s unnecessary. The logic of SPFA is that we only relaxed the node’s out-edges when it is updated. Because if the node doesn’t be updated, its out-edges won’t be relaxed. We can maintain a queue to control which node should be relaxed. In Bellman Ford, we know that the node will be updated $dots$ times at most, so if a node enter the queue beyond n times, that means there is a Negative Weight Cycle. If a node is in the queue, there is no need to enter it again because when pop it, it will updated. If the node out of the queue is a better one, it will enter the queue at next time. And we can also use priority queue too, and there is no obvious difference.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
vector<vector<pair<int, int>>>adj;
void init()
{
adj = vector<vector<pair<int, int>>>(1000);
}
void addEdge(int u, int v, int w)
{
adj[u].push_back({v, w});
}
bool SPFA(int start, int dots)
{
vector<bool>check(1000, false);
check[start] = true;
vector<int>dist(1000, INT_MAX);
dist[start] = 0;
vector<int>count(1000, 0);
queue<int>q;
q.push(start);
while(!q.empty())
{
int u = q.front(); q.pop();
check[u] = false;
for(auto [v, w] : adj[u])
{
if(dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
if(!check[v])
{
q.push(v);
check[v] = true;
count[v]++;
}
if(count[v] > dots) return false;
}
}
}
return true;
}