Floyd Warshall algorithm
import sys
INF=sys.maxsize
def warshall(graph):
n = len(graph)
dist = [[] for i in range(n)] #to store result
for i in range(0,n):
for j in range(0,n):
dist[i].append(graph[i][j])
for i in range(n):
for j in range(n):
for k in range(n):
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
print('Shortest Distance between every pair of vertex:-')
for i in range(n):
for j in range(n):
if dist[i][j]==INF:
print ("%7s" % ("INF"),end='\t')
else:
print ("%7s" % (dist[i][j]),end='\t')
print()
graph = [[0,5,INF,10],[INF,0,3,INF],[INF,INF,0,1],[INF,INF,INF,0]]
warshall(graph)
import sys
INF=sys.maxsize
graph = [[0,5,INF,10],[INF,0,3,INF],[INF,INF,0,1],[INF,INF,INF,0]]
def warshall(graph):
n = len(graph)
dist = [[] for i in range(n)] #to store result
for i in range(0,n):
for j in range(0,n):
dist[i].append(graph[i][j])
for i in range(n):
for j in range(n):
for k in range(n):
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
print('Shortest Distance between every pair of vertex:-')
for i in range(n):
for j in range(n):
if dist[i][j]==INF:
print ("%7s" % ("INF"),end='\t')
else:
print ("%7s" % (dist[i][j]),end='\t')
print()
print("original Graph is ")
n= len(graph)
for i in range(n):
for j in range(n):
if graph[i][j]==INF:
print ("%7s" % ("INF"),end='\t')
else:
print ("%7s" % (graph[i][j]),end='\t')
print()
warshall(graph)
