Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is a method designed to find the shortest paths between all pairs of nodes 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 independently by Robert Floyd and Stephen Warshall in 1962.

The Floyd-Warshall Algorithm uses a stepwise approach to determine the shortest paths between all pairs of nodes in a graph. At each step, it updates the shortest paths by introducing an intermediate node.

1- Initialization:

• The graph’s adjacency matrix is used, which 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 considers each node as an 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 iteratively uses each node as an intermediate node and updates the distances at each step.
• This process continues until all nodes have been used as intermediate nodes.

4- Result:

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

class=\

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.

• 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.