Skip to main content

Floyd-Warshall Algorithm

1. What is the Floyd-Warshall Algorithm?​

The Floyd-Warshall Algorithm is used to find the shortest paths between all pairs of vertices in a weighted graph. It works for both directed and undirected graphs and can handle graphs with negative weight edges, but not negative weight cycles.

2. Algorithm for Floyd-Warshall Algorithm​

  1. Initialize the distance matrix with the weights of the edges between vertices.
  2. For each pair of vertices (i,j)(i, j), update the distance matrix by considering the possibility of going through a third vertex (k)(k) to get a shorter path from ii to jj.
  3. The final distance matrix will contain the shortest distances between all pairs of vertices.

3. How Does Floyd-Warshall Algorithm Work?​

  1. Start with a distance matrix representing the weights of the edges between vertices.
  2. Update the matrix by considering all possible intermediate vertices for each pair of vertices.
  3. Repeat this process until all pairs of vertices have been considered, and the matrix stabilizes.

4. Problem Description​

Given a weighted graph, the Floyd-Warshall Algorithm aims to find the shortest paths between all pairs of vertices in the graph.

5. Examples​

Example graph:

      0    1    2    3
--------------------
0 | 0 3 ∞ 7
1 | 8 0 2 ∞
2 | 5 ∞ 0 1
3 | 2 ∞ ∞ 0

6. Constraints​

  • The graph can have negative weight edges, but not negative weight cycles.

7. Implementation​

def floyd_warshall(graph):
V = len(graph)
dist = [[float('inf') for _ in range(V)] for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for u in range(V):
for v in range(V):
if graph[u][v] != 0:
dist[u][v] = graph[u][v]
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist

8. Complexity Analysis​

  • Time Complexity: O(V3)O(V^3), where VV is the number of vertices.
  • Space Complexity: O(V2)O(V^2), for storing the distance matrix.

9. Advantages and Disadvantages​

Advantages:​

  • Finds the shortest paths between all pairs of vertices.
  • Can handle graphs with negative weight edges.

Disadvantages:​

  • Inefficient for large graphs due to its cubic time complexity.
  • Requires additional space to store the distance matrix.

10. Reference​