Shortest Path Algorithms

In this lesson we will learn about 2 very useful shortest paths algorithms - Bellman Ford and Floyd Warshall

Bellman Ford

Remember the one limitation that Dijkstra's algorithm had - weights can not be negative, Bellman Ford fixes that!

Lets first look at the shortest path between any two nodes,

It can have, at most n-1 edges! (If it had any more, it would form an unnecessary cycle)

This means that we are guaranteed to find the shortest path by comparing all the nodes n-1 times!

How do we compare them?

Comparing them is as simple as checking if we can get from one node to another faster: if (dist[i] < dist[j] + w) -> update the distance

One more thing to consider is a case when no path exists: Negative Weight Cycles

There is no shortest path here, going from A to B to C always reduces the path by 3, this means that we can repeat doing this infinitely and get a $-\infty$ length.

Bellmen Ford can detect this - If a solution is not found in n-1 steps, then there exists a Negative Weight Cycle

Code:

Literally just 2 for loops:

//adj[i] is assumed to be {from, to, weight}, the code can easily be adapted to any other representation, this is usually the simplest one
vector<int> bellmanFord(int n, vector<vector<int>>& adj) { 
    
	vector<int> dist(n, 1e8);
	dist[0] = 0;
  
	for (int i = 0; i < n; i++) {
	    
		for (vector<int> edge : adj) { 
		
			int from = edge[0];
			int to = edge[1];
			int w = edge[2];
			
			if (dist[from] != 1e8 && dist[from] + w < dist[to]) {
			    
                if(i == n - 1)
                    return {-1}; // A negative weight cycle
               
                dist[to] = dist[from] + w;
            }
		}
	}

    return dist;
}

Time complexity: O( V * E ) - where V is the number of verticies(nodes) and E the number of edges

Floyd Warshall

Another really useful algorithm is Floyd Warshall, it lets us get the shortest path between all nodes in O($n^3$).

Just like with Dijkstra, the weights can not be negative!

The idea is as brute force as it gets, start with a 2d matrix of connections:

If to get from any node A to any other node B, we pass through node C, then we can assume that if AB is optimal, AC and CB also have to be optimal!

Now lets treat each node as a C, aka, lets see how many other nodes does the current node connect. (We will do this in order from 0 to n, this guarantees that when we compute the current C it is as best as it can be right now)

Now we can simply do a triple for loop, for each possible intermediate node C, try every other node as a A and for each of those try every other node as a B, if something improves improve it.

When we get to C == n we have solved the problem.

Code:

void floydWarshall(vector<vector<int>> &dist, int n) {

    int INF = 1e8;

    // for each intermediate vertex
    for (int c = 0; c < n; c++) {

        // Pick all vertices as source one by one
        for (int a = 0; a < n; a++) {

            // Pick all vertices as destination, for the above picked source
            for (int b = 0; b < n; b++) {

                // shortest path from i to j 
                if(dist[a][c] != INF && dist[c][b]!= INF ){
                
	                dist[a][b] = min(dist[a][b], dist[a][c] + dist[c][b]);
                }
                    
            }
        }
    }
}

Time complexity: O($n^3$)

We also could have solved this by running Dijkstra from every node.

Floyd Warshall is better when the graph is dense(has lots of edges), and Dijkstra from every node is better for sparse graphs. Nevertheless because of its implementation simplicity, Floyd Warshall is most commonly used!