Shortest Path Algorithms

The shortest path problem is about finding a path between 2 vertices in a graph such that the total sum of the edges weights is minimum.

Bellman Ford's Algorithm

Bellman Ford's algorithm is used to find the shortest paths from the source vertex to all other vertices in a weighted graph.

Shortest path contains at most n - 1 edges, because the shortest path couldn't have a cycle.

A very important application of Bellman Ford is to check if there is a negative cycle in the graph.

Algorithm Steps:

• The outer loop traverses from 0 : n − 1.

• Loop over all edges, check if the next node distance > current node distance + edge weight, in this case update the next node distance to "current node distance + edge weight".

Time Complexity: O(V E)

Dijkstra's Algorithm

Dijkstra's algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph.

Algorithm Steps:

• Set all vertices distances = infinity except for the source vertex, set the source distance = 0.

• Push the source vertex in a min-priority queue in the form (distance , vertex), as the comparison in the min-priority queue will be according to vertices distances.

• Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).

• Update the distances of the connected vertices to the popped vertex in case of "current vertex distance + edge weight < next vertex distance", then push the vertex with the new distance to the priority queue.

• If the popped vertex is visited before, just continue without using it.

• Apply the same algorithm again until the priority queue is empty.

Time Complexity: O(V^2) O(V + E log V) with min-priority queue

On every iteration of the algorithm, a vertex is added with the minimum distance from the source and one that does not exist in the current shortest path.

Floyd-Warshall's Algorithm

Floyd-Warshall's Algorithm is used to find the shortest paths between between all pairs of vertices in a graph, where each edge in the graph has a weight which is positive or negative.

The Algorithm Steps:

For a graph with N vertices:

• Initialize the shortest paths between any 2 vertices with Infinity.

• Find all pair shortest paths that use 0 intermediate vertices, then find the shortest paths that use 1 intermediate vertex and so on.. until using all N vertices as intermediate nodes.

• Minimize the shortest paths between any 2 pairs in the previous operation.

• For any 2 vertices (i,j) , one should actually minimize the distances between this pair using the first K nodes, so the shortest path will be: min(dist[i][k]+dist[k][j],dist[i][j]).

dist[i][k] represents the shortest path that only uses the first K vertices i, k, dist[k][j] represents the shortest path between the pair k, j. As the shortest path will be a concatenation of the shortest path from to i to k, then from k to j.

Time Complexity: O(V^3)