Single Source Shortest Path : A Deep Dive

The Problem

Given a source in a graph you have to find the shortest path to all other nodes .

The Existence of Shortest Path

The shortest path exists when there is no negative weight cycle . This is pretty much intuitive . Whenever there is a negative weight cycle we can traverse that cycle and our shortest path will decrease . We can do that infinite amount of times .
Thus leads to having no shortest path .

Bruteforce

If we were to solve this by bruteforce , we can use BFS for every possible path to a node and take the shortest one .

Complexity : O( number of paths * (E + V) )

Now , the number of paths can be exponential . So , we can not solve this problem efficiently

Bellman Ford Algorithm

Bellman and Ford were the first few persons to tackle this problem . The Algorithm uses 2 simple facts :

• The shortest path is always a simple path
• The shortest simple path to any node contains at most n nodes connected by n-1 edges

Using these 2 simple facts they devised the algorithm . The pseudocode is as folows :

for iteration 1 to n-1:
    relax all edges u->v 

Now , what is this edge relaxation and why are we doing this relaxation n-1 times ? Let’s see why

Edge Relaxation

The main operation for all shortest path finding algorithms is this edge relaxation process . The main idea is , if in the current stage of the algorithm we have the opportunity to shorten the shortest path to a node , we do that .

relax(u,v) :
    if Distance[u] + weight(u,v) < Distance[v] : # the path can be shortened
        Distance[v] = Distance[u] + weight(u,v) # relaxing the edge

Now , why are we doing this n-1 times for each edge ?

After we relax an edge the shortest path to that vertex is length of the shortest path of the vertex that relaxed the edge + 1 . Let’s see a simple example for better understanding :

If we were to simulate Bellman Ford Algorithm on this graph ,

Iteration 1

We relaxed s -> a and s -> c . Our shortest path to a and c increased to 1 .

Iteration 2

We relaxed a -> b . So shortest path to b is now 2 .

Iteration 3

We can further relax b -> c . Now the shortes path to c increased to 3 .

Now , we can clearly see why are doing the iteration n-1 times . For a shortest path to exist to any node it can not have a path containing more than n-1 edges .
We can clearly see fro the simulation , after ith iteration we get the shortest path with atmost i edges . That’s why we are doing this relaxation step n-1 times .

Complexity Analysis

Complexity is pretty much straighforward : O( V * E )

Worst Case Behaviour

Edges are in the list in worst order
3 -> 4 , 2 -> 3 , 1 -> 2 , 0 -> 1

Can you think of any way to optimize Bellman Ford’s Algorithm ?

Optimization Idea 1

If during the current step no edge is relaxed , then we have found the shortest path to all the nodes as in the next iteration nothing will improve as there simply is no candidate to improve .
So , if no relaxation is made we can terminate . The worst case complexity remains same .

Optimization Idea 2

I think you have already noticed in that small simulation we are not relaxing all the edges in the current iteration . So , if we were able to keep track of the elements that are potential candidate to improve their neighbors we are in luck of optimizing the algorithm . We can modify the Bellman Ford Algorithm using a queue to do that . It is more like a modified BFS . We will also use adjacency list representation to improve the runtime .

Types of graphs where Bellman Ford gives correct result

Given that a shortest path exist , Bellman Ford always gives the correct result . It is one of it’s advantage .

 

Dijkstra’s Algorithm

Unlike Belman Ford’s SSSP Algo Dijkstra’s SSSP Algorithm doesn’t work on graphs with negative edge weights . Apart from that Dijkstra’s Algorithm is much faster in graphs in most real life scenerio where weights are usually distance or time .

The Algorithm uses a simple greedy apraoch . The idea is as follows :

• maintain a set of nodes where the algorithm has already determined the shortest path
• from the explored set of nodes find the one with minimum distance, relax adjacent edges

The pseudocode is as follows :

for i 1 to number_of_nodes : 
    distance[i] = INF

distance[source] = 0

populate all the {distance[node],node} pairs in a data structure

while the data structure is not empty :
    u = the node with minimum distance
    extract(u)
    for every v in neghborhood of u :
        relax edges u->v

 

Complexity Analysis

 

Original Dijkstra Implementaion : O(V^2)

Uses Array as the data structure .

• Initialize distances : O(V)
• Populate Data Structure : O(V)
• Extract Min : for each node O(V) . Across all nodes O(V^2)
• Adjacency list update : across all nodes atmost E updates , Each update is O(1) . So , Across all nodes O(E)

So , overall complexity : O(V^2)

 

Efficient Dijkstra Implementaion : O(ElogV)

Uses Binary Heap as the data structure .

• Initialize distances : O(V)
• Populate Data Structure : Build Heap O(V)
• Extract Min : Find min O(1) and Delete Min (heapify) O(logV) . So for each node O(logV) and Across all nodes O(VlogV)
• Adjacency list update : across all nodes atmost E decrease key updates , Each update is O(logV) . So , Across all nodes O(ElogV)

So , complexity : O( VlogV + ElogV ) = O(ElogV)

 

Most Efficient Dijkstra Implementaion : O(VlogV)

Uses Fibonacci Heap as the data structure .

• Initialize distances : O(V)
• Populate Data Structure : Build Heap O(V)
• Extract Min : Find min O(1) and Delete Min O(logV) . So for each node O(logV) and Across all nodes O(VlogV)
• Adjacency list update : across all nodes atmost E decrease key updates , Each update is O(1) . So , Across all nodes O(E)

So , complexity : O( VlogV + E) = O(VlogV)

 

Summary

 

	Initialize	Populate	Extract Min	Adjacency List Update	Total Complexity
Array	O(V)	O(V)	O(V^2)	O(E)	O(V^2)
Binary Heap	O(V)	O(V)	O(VlogV)	O(ElogV)	O(ElogV)
Fibonacci Heap	O(V)	O(V)	O(VlogV)	O(E)	O(VlogV)

 

Shortcomings

Dijkstra’s Algorithm can fail on graphs with negative weights_ . Because of the greedy approach we take , whenever we are done processing a node by extracting , we have found the _optimal subpath for that node . But if a graph has negative weights , latter is not true .

Here is an example :

Try simulating to see why Dijkstra fails in this case and also for which vertex .

 

Modified Dijkstra’s Algorithm

Modified Dijkstra’s Algorithm does not works on negative weighted graph .

The idea is as follows :

• Instead of pre populating the heap , we start from source and each time take the one with minimum distance
• Relax the adjacent edges of the chosen node and if the edge is able to minimize the distance we again insert the minimized node .

The pseudocode is as follows :

for i 1 to number_of_nodes : 
    distance[i] = INF

distance[source] = 0

insert {distance[source],source} in heap

while heap is not empty :
    u = the node with minimum distance
    extract(u)
    for every v in neghborhood of u :
        if edge u->v relaxed :
            insert {distance[v],v} in heap

In the implementation , we use a trick called Lazy Update . We leave the outdated bigger valued weights in the Heap as it is instead of deleting it . As the next time we encounter this node we will surely meet the one with the smaller weight first

Complexity Analysis

For non negative weighted graph , the complexity is the same as the original Dijkstra .

As for the graphs with negative weights . It is tough to assign a proper upperbound as it is possible to design graphs with exponential number of operations .

Special Graphs | Already Known Algorithms

Unit Edged Graph

A simple BFS is sufficient

Can you see why ?

Answer

If all edges have weight 1 , it is easy to see that shortest path is nothing but the level of the node

Tree

The tree can be weighted/unweughted . A simple BFS/DFS is sufficient .

Can you see why ?

Answer

In a tree , there is only one path from one node to another . So , the distance from the source is indeed the shortest distance .

DAG (Directed Acyclic Graph)

If you noticed the 2nd Bellman Ford Optimization , we can reduce the complexity of the shortest path algorithm by cleverly choosing edges to update .

For a DAG , if we find the topsort order and process the edge relaxation in that order , we will always go in the optimized direction as topsort guarantees that .

The pseudocode is as follows :

order = Topsort(graph)

while order is not empty :
    u = front element of order
    Extract(u)
    for every v in neghborhood of u :
        relax edges u->v

Works on negative edge weighted graph also .

Complexity

Topsort : O(V+E)
Edge Relaxation in Topsort Order : O(E)
So , Complexity : O(V+E)