What is the Floyd-Warshall algorithm?
The Floyd-Warshall algorithm, introduced in 1962 by Robert Floyd and Stephen Warshall, is a graph algorithm employed to determine the shortest paths connecting all pairs of vertices in a weighted graph.
Algorithmic explanation
This algorithm is based on dynamic programming and operates on a matrix representation of the graph, where each entry represents the shortest distance between two vertices. Initially, the matrix is filled with the direct distances between the vertices. The distance is set to infinity for pairs of vertices that are not directly connected.
The algorithm then iterates through all vertices and considers each vertex as a possible intermediate vertex in the shortest path between two other vertices. For each pair of vertices , it checks if going through the intermediate vertex reduces the distance from to . If it does, the distance is updated with the new shorter distance.
The algorithm repeats this process for all vertices because possible intermediate vertices gradually build up the shortest paths until the final matrix contains the shortest distances between all pairs of the vertices. It also keeps track of the intermediate vertices on the shortest paths to reconstruct the actual paths if needed.
Coding implementation
The following code demonstrates the implementation of the Floyd-Warshall algorithm on a general graph. This code is designed to output the shortest distances between all pairs of vertices in the graph.
# Number of vertices in the graphV = 4# Function to print the final solution matrixdef printSolution(dist):print("Shortest distances between all pairs of vertices:")for i in range(V):for j in range(V):if dist[i][j] == float('inf'):print("INF", end="\t")else:print(dist[i][j], end="\t")print()# Function that implements the Floyd-Warshall algorithmdef floydWarshall(graph):dist = [[float('inf') for _ in range(V)] for _ in range(V)]# Initialize the distance matrix with direct distancesfor i in range(V):for j in range(V):dist[i][j] = graph[i][j]# Update distances using all vertices as intermediate nodesfor 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])# Print the shortest distancesprintSolution(dist)# Example graph represented by an adjacency matrixgraph = [[0, 5, float('inf'), 10],[float('inf'), 0, 3, float('inf')],[float('inf'), float('inf'), 0, 1],[float('inf'), float('inf'), float('inf'), 0]]# Run the algorithmfloydWarshall(graph)
Explanation
- Line 2: We set the number of vertices
Vto 4. - Lines 5–13: The
printSolution()function prints the shortest distances between all pairs of vertices, represented by thedistmatrix, withINFindicating infinity. - Lines 16–31: We implement the Floyd-Warshall algorithm.
- Lines 34–38: We generate an example graph for implementing the algorithm.
Time complexity
The time complexity of the Floyd-Warshall algorithm can be expressed as , where denotes the total count of vertices present in the graph. It is suitable for dense or small graphs where the number of vertices is relatively small.
Free Resources
