## 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-23 by Andrey BRATUS, Senior Data Analyst.

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.

1. ## Floyd-Warshall Algorithm Python code:

2. ``````
# 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))

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)
``````