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.
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.
Floyd-Warshall Algorithm Python code:
# 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)
