Floyd-Warshall use case.
In Computer Sciense the Floyd-Warshall Algorithm is an algorithm for finding the shortest paths between all the pairs of vertices in a weighted graph. It is also called as Roy-Floyd algorithm, Roy-Warshall algorithm or WFI algorithm. A single execution of the algorithm is sufficient to find the lengths of the shortest paths between all pairs of vertices.
Python Knowledge Base: Make coding great again.
- Updated:
2024-07-26 by Andrey BRATUS, Senior Data Analyst.
Floyd-Warshall Algorithm Python code:
Floyd-Warshall Algorithm code result:
It works for the directed and undirected weighted graphs, but it does not work for the graphs with negative cycles. The Floyd-Warshall algorithm is a good example of dynamic programming, which breaks the problem down into several smaller subproblems and then combines the answers to those subproblems to solve the initial problem.
# number of vertices
nV = 4
# Define infinity as a large number
INF = 99999
# main function
def FloydWarshall(G):
distance = list(map(lambda i: list(map(lambda j: j, i)), G))
# Adding vertices
for k in range(nV):
for i in range(nV):
for j in range(nV):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
print_solution(distance)
# Print the solution
def print_solution(distance):
for i in range(nV):
for j in range(nV):
if(distance[i][j] == INF):
print("INF", end=" ")
else:
print(distance[i][j], end=" ")
print(" ")
G = [[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]
]
print ("Shortest distances between every pair of vertices:\n")
FloydWarshall(G)
