Queue Optimized Bellman-Ford Algorithm

Introduction


Let’s talk about single-source shortest paths. If you are given a weighted graph and a starting node, how do you find the shortest paths to every other node on the graph? 

Dijkstra’s algorithm? Yes, but what about graphs with negative edges like the one above? You might remember that Dijkstra’s greedy strategy cannot handle negative edges. In competitive programming, there is another popular algorithm that is slightly slower than Dijkstra’s but is much easier to implement and is capable of handling negative edges — Bellman-Ford algorithm. In this article, we will talk about queue optimized Bellman-Ford algorithm, which is also known, to some Chinese scholars, as Shortest Path Faster Algorithm(SPFA). For Simplicity, I will just refer to it as SPFA in the following content. Let’s get started! 

1. Core Idea


Just like many other shortest path algorithms, SPFA assumes the distances to all nodes to be infinity before doing anything. It is as if all other nodes are disconnected to the starting node. Then, by exploring the edges, SPFA gradually shortens the distances until there is no room for further optimization. In this distance updating process, SPFA maintains an examine queue, which is the heart of the algorithm. The queue stores nodes that have to be examined for distance update. And SPFA terminates when the queue empties, which indicates that there is no further possible optimization.

That is just an overview of the algorithm. It’s totally fine if you are still confused. Just like I said, the examine queue is the heart of the algorithm. If you understand the queue, you understand SPFA. Let’s walk through an analogical example to see how the examine queue is maintained.

Consider a technician Dave whose job is to collect malfunctioning parts in a batch of old cars. The cars come in a queue. Dave can identify a defective car by running a quick test, but the tests won’t tell him exactly which part of the car is malfunctioning. The only way to do that is to disassemble the car and check each of its parts. If an integrated part contains multiple sub-parts, for example, the engine, he would have to disassemble it as well to locate the real malfunctioning part, which could be as small as a tiny gear inside the engine. Dave is a smart worker. He doesn’t like to work in the orthodox way, which means only moving on to the next car after locating the exact malfunctioning parts of the previous car. Instead, he works like this:

  • If the quick test shows that a car/integrated part is defective, Dave disassembles it and put the sub-parts at the end of the queue then move on to the next item.
  • If an item is defective and cannot be disassembled into smaller parts, pick it out and move on to the next item. 

As you may have guessed, the queue of cars in our example stands for the examine queue in SPFA. The idea is that we only push a part’s sub-parts to the examine queue if the quick test shows that it is defective. This is the core idea of maintaining the examine queue in SPFA: if we find a shorter path to a node S, that means the current distance value we have for this node is not good enough, or “defective.” Therefore after we shorten its distance value, it is necessary to check for distance updates on its adjacent nodes, so we push S to the end of our examine queue. 

The queue structure may remind you of Breadth-First Search(BFS). Admittedly, there are some similarities. But SPFA pushes a node into the queue not when it’s discovered, but when its distance is shortened, or, as some may call it, relaxed, and SPFA may push a node into the examine queue multiple times. The commonality is that they both terminate on the exhaustion of the queue.

2. Example


One of the problems with many SPFA articles online is that they confuse readers by tracing the algorithm on complicated graphs. It’s really hard to get the intuition of the algorithm when you cannot even tell which node is which. Let’s walk through an example on a small graph to give you the essence of how SPFA works before diving into detailed C++ implementations. 

Let’s say Bill just arrived in a new town and decided to explore it. He discovered that from where his location, there is a direct road to the theater which has a big traffic jam and a roundabout freeway which goes through the farm. He also found that the only way to get to the police station is to get to the theater first. Bill just learned SPFA and wants to find out the fastest way to get to each of these locations in the city. Notice that the edge weights here represent travel time rather than physical distance, but for consistency, let’s just call them distance. 

Initially, SPFA assumes that all the nodes are disconnected from the starting node. Then it pushes the starting node into the examine queue to kick start the relaxation process.

After that, it examines the first item in the queue and updates distances to its adjacent nodes. If a node’s distance is updated, that means our distance record for it is defective, which means we also need to examine that node’s adjacent nodes later, which means we push it into the examine queue. You can see it here that if a node is in the examine queue, that means this node has the possibility to bring distance updates to its adjacent nodes. 

And repeat this process until we exhaust the examine queue, which indicates that there is no node with the possibility to shorten our current distance value, which means we have already found the shortest path to all the nodes on the graph. 

Pause! Take a look at the graph.

You can see that at this point, SPFA found a shorter path to the theatre, which is the path through the farm. We’ve relaxed the distance to the theatre, which means for theatre’s successor nodes, in this case, the police station, their distances could also be defective, because we used the traffic jam road to the theatre when calculating their distances! So, we push theatre to the examine queue to use the shorter path we have found to update its predecessor nodes later. 

And when the queue is empty, the algorithm terminates. We got our answer.

3. Detect Negative Cycles


As we mentioned before, SPFA can handle graphs with negative weight edges. However, a graph has no shortest path if it contains a negative cycle, which means a cycle the edge weight sum of which is a negative number because distance can get infinitely smaller by looping in the negative cycle. 

In the example above, there is no shortest path to the theatre. The more times Bill walks through the cycle, the less total distance he yields. Does this mean that our algorithm may fail? No. We can design a terminate condition for our algorithm, which detects negative cycles.

Since a negative cycle will cause our examine queue never to be exhausted, it will result in an infinite loop. Therefore, the first  and easiest solution is to set a high ceiling for the number of nodes that have been pushed into the queue. For example, if there are more than |v| times |e| nodes pushed into the queue, terminate the algorithm and print “No Solution.” Because |V|·|E| (number of vertices times number of edges)is the worst-case runtime of the algorithm.

If we want to be more efficient, we can keep track of the number of edges we used to get to each node. If any number exceeds |V| – 1, we know the path has looped in some negative cycle. Where this boundary come from? I don’t want to confuse you with some mathematical proof. Just think about it. If a graph is connected, it is possible to get to any node from a starting point with at most |V|-1 edges. Think about a linked list! A linked list with three nodes contains two “edges.” If a path contains more than |V|-1 edges, that means it must have visited some nodes twice, which means it must contain loops. And it cannot be a positive loop because positive loops increase total distance. Our algorithm never chooses longer paths. Therefore it has to be negative loops that decrease distance.

4. Implementation


Let’s talk about how you can implement SPFA at contests. Notice that if you are not familiar with competitive programming graph construction techniques. Please refer to this article.

First of all, for graphs without negative loops.

You could implement the algorithm like this. 



#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#define maxn 1005
#define maxm 100005

using namespace std;


//struct for directed edge
struct Edge{int to,w;}; 
//Adjacency list.
vector<Edge> adj[maxn]; 
//Examine queue
queue<int> q;
int n,m;
//dist[i] stores distance to node[i]
int dist[maxn];
//inq[i] stores wether node i is in queue
bool inq[maxn]; 


//read input data and build graph
void init(){
	scanf("%d%d",&n, &m);
	for(int i = 1; i <= m; i++){
		int x,y,z; scanf("%d%d%d", &x, &y, &z);
		adj[x].push_back((Edge){y,z});
	}
	//Initialize distance to every node to infinity
	memset(dist, 127, sizeof(dist));
}

void spfa(){
	inq[1] = true; q.push(1); dist[1] = 0;
	while(!q.empty()){
		int t = q.front(); q.pop(); inq[t] = false;
		for(int i = 0; i < adj[t].size(); ++i){ //traverse all the outgoing edges
			int tn = adj[t][i].to; 
			if(dist[tn] > dist[t] + adj[t][i].w){ //If there is room for relaxation
				dist[tn] = dist[t] + adj[t][i].w;
				//If the node relaxed is not in the queue, add it to the queue.
				if(!inq[tn]){inq[tn] = true; q.push(tn);}
			}
		}
	}
}

int main(){
	init();
	spfa();
	
	//Print answer
	for(int i = 2; i <= n; i++){
		cout << dist[i] << endl;
	}
	return 0;
}


And for graphs with negative cycles, just add an array cnt[i] to store the edges used to get to the i-th node. 



//Queue optimized bellman-ford with negative cycle detection
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#define maxn 1005
#define maxm 100005

using namespace std;


//struct for directed edge
struct Edge{int to,w;}; 
//Adjacency list.
vector<Edge> adj[maxn]; 
//Examine queue
queue<int> q;
int n,m;
//dist[i] stores distance to node[i]
int dist[maxn];
//inq[i] stores wether node i is in queue
bool inq[maxn]; 


//cnt[i] stores the edges used to get to i
int cnt[maxn]


//read input data and build graph
void init(){
	scanf("%d%d",&n, &m);
	for(int i = 1; i <= m; i++){
		int x,y,z; scanf("%d%d%d", &x, &y, &z);
		adj[x].push_back((Edge){y,z});
	}
	//Initialize distance to every node to infinity
	memset(dist, 127, sizeof(dist));
}

bool spfa(){
	inq[1] = true; q.push(1); dist[1] = 0;
	while(!q.empty()){
		int t = q.front(); q.pop(); inq[t] = false;
		for(int i = 0; i < adj[t].size(); ++i){ //traverse all the outgoing edges
			int tn = adj[t][i].to; 
			if(dist[tn] > dist[t] + adj[t][i].w){ //If there is room for relaxation
				dist[tn] = dist[t] + adj[t][i].w;
				
				/*Check for negative cycle*/
				cnt[tn] = cnt[t] + 1;
				if(cnt[tn] > n-1) return false;
				
				
				//If the node relaxed is not in the queue, add it to the queue.
				if(!inq[tn]){inq[tn] = true; q.push(tn);}
			}
		}
	}
	return true;
}

int main(){
	init();
	
	//Print answer
	if(spfa()){
	  for(int i = 2; i <= n; i++){
		  cout << dist[i] << endl;
	  } 
	}else{
	    cout << "No Solution";
	}
	return 0;
}

Summary


The worst-case complexity of SPFA is O(|V||E|), which is dangerous on dense graphs. There are shortest path contest problems the test data of which are designed specifically to stop SPFA. It is safer to use Dijkstra’s algorithm when the graph is big and contains no negative weight edges. But queue optimized bellman-ford guarantees quick AC on small graph problems, and, most importantly, graphs with negative edges. 


Copyright © 2019 by Kangmin Tan. All rights reserved.

For permission to reprint articles from this site, please contact kangmint@usc.edu.

%d bloggers like this: