Day-25: Floyd-Warshall All Pairs Shortest Path ALgorithm

Floyd-Warshall is a shortest path algorithm just like Dijkstra and Bellman Ford. However, it computes the shortest paths between each and every one of the pairs in a weighted graph.

It works on non-negative weighted graphs.

The algorithm is very straightforward.

It takes a graph as an adjacency matrix and iterates through every possible triplets of vertices.

If including a node in a path is reasonable, it takes it. If not, it does not.

The recurrence relation looks like this:

*d[u][v] = min(d[u][x] + d[x][v], d[u][v])*

Time complexity: O(V^3)

Here is the link of my C++ implementation of Floyd-Warshall Algorithm: Floyd-Warshall Algorithm