Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is an algorithm designed to find the shortest paths between all pairs of knot in graph theory. This algorithm employs a dynamic programming approach and can operate on graphs with both positive and negative edge weights, provided there are no negative-weight cycles. The algorithm was developed in 1962 by Robert Floyd and Stephen Warshall independent.

Working Principle

The Floyd-Warshall Algorithm uses a stepwise approach to find the shortest paths between all pairs of nodes in a graph. At each step, it updates the shortest paths by considering one intermediate node at a time.

1- Initialization:

• The graph’s adjacency matrix is used. This matrix contains the direct edge weights between nodes.
• If there is no direct edge between two nodes, the distance is set to infinity (∞).
• The distance from each node to itself is set to 0.

2- Dynamic Programming Approach:

• The algorithm iterates through each node as a potential intermediate node and updates the distances between all pairs of nodes.
• In each step, a node k is selected as the intermediate node, and the following formula is applied to all node pairs (i,j): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Where:

• dist[i][j]: the current shortest distance between nodes i and j.
• dist[i][k]: the distance between nodes i and k.
• dist[k][j]: the distance between nodes k and j.

3- Processing All Intermediate Nodes:

• The algorithm iterates through all nodes sequentially as intermediate nodes, updating distances at each step.
• This process continues until every node has been used as an intermediate node.

4- Result:

• When the algorithm completes, the dist[i][j] matrix contains the shortest distances between all pairs of nodes (i,j).

Floyd-Warshall Algorithm example

Floyd-Warshall Algorithm in Java Code

Time Complexity

The time complexity of the Floyd-Warshall Algorithm is O(V³), where V represents the number of nodes. This means the algorithm can be slow for large graphs, but it remains an effective method for computing shortest paths between all pairs of nodes.

Limitations

• Negative-Weight Cycles: The algorithm does not produce correct results for graphs containing negative-weight cycles.
• Large Graphs: Due to its O(V³) time complexity, it is inefficient for very large graphs.