Floyd’s Algorithm

Basics and Definition

Floyd’s Algorithm is a graph analysis algorithm used to find shortest paths between all pairs of nodes in a weighted graph.
The algorithm works by iteratively improving an estimate on the shortest path between two vertices, until ultimately obtaining the shortest path.

Floyd’s algorithm considers all possible paths between pairs of vertices.
It is significant for its ability to handle both negative and positive edge weights effectively.
Due to its high computational complexity, it is used primarily for small datasets or circumstances where the dense graph structure justifies its use.

Floyd’s algorithm maintains a matrix dist[ ][ ], such that dist[i][j] contains the shortest distance from the vertex i to vertex j.
It initializes dist[i][j] = INFINITY for all vertex pairs (i, j) to infinity, except for dist[i][i] = 0 where i equals j.
At the start the shortest distance between each pair of vertices is the direct edge between them, if it exists.
Floyd’s algorithm compares all possible paths in the graph between each pair of vertices and calculates the shortest of them.

Floyd’s Algorithm has a time complexity of O(V^3) given that V is the number of vertices in the graph. This is because the algorithm uses three nested loops to traverse each vertex.
Despite its cubic time complexity, it is often the algorithm of choice for solving all pairs shortest path problems since the simple data structures and operation per iteration are suitable for dense or small graphs.