Floyd-Warshall Algorithm

Introduction: The Floyd-Warshall Algorithm is a dynamic programming technique used to find the shortest paths between all pairs of vertices in a weighted graph. It is particularly useful for dense graphs and works for both directed and undirected graphs.

How does it work?

• Initialize the distance matrix with direct edge weights between vertices. If no edge exists, set the distance to infinity.
• Iteratively update the distance matrix by considering each vertex as an intermediate point.
• For each pair of vertices (i, j), check if the path through an intermediate vertex k is shorter than the current known path.
• Update the distance matrix accordingly.

Key Observations:

• The algorithm uses a distance matrix to store shortest path distances.
• It iteratively refines the shortest paths by considering all possible intermediate vertices.
• Handles negative edge weights but does not work with negative weight cycles.

Algorithm Steps:

• Initialize the distance matrix with edge weights and set diagonal elements to zero.
• For each vertex k, update the distance for all pairs (i, j) using the formula:
  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
• Repeat until all vertices have been considered as intermediate points.

Advantages:

• Simple and easy to implement.
• Works for both directed and undirected graphs.
• Handles graphs with negative edge weights (no negative cycles).

Disadvantages:

Time Complexity:

• Time Complexity: O(V³), where V is the number of vertices.
• Space Complexity: O(V²) for the distance matrix.