fork download
copy 
  1. import sys
  2. class Graph:
  3. 	def __init__(self,graph,edge):
  4. 		self.graph=graph
  5. 		self.edge=edge
  6.  
  7. 		self.w=[[sys.maxsize]*len(self.graph) for i in range(len(self.graph))]
  8. 		for i in range(len(self.w)):
  9. 			for j in range(len(self.w)):
  10. 				if(i==j):self.w[i][j]=0
  11. 				if self.edge.get( (i,j) ): self.w[i][j]=self.edge[i,j]
  12.  
  13. 	def Floyd_Warshall(self):
  14. 		n=len(self.w)
  15. 		D=[list(self.w)for i in range(n)]
  16. 		D0=list(self.w)
  17. 		p0=[[0]*n for i in range(n)]
  18. 		p=[list(p0) for i in range(n)]
  19. 		for i in range(n):
  20. 			for j in range(n):
  21. 				if i==j or not self.edge.get( (i,j) ) : p0[i][j]=None
  22. 				else: p0[i][j]=i
  23. 		print(p0)
  24. 		for k in range(len(D)):
  25. 			for i in range(0,n):
  26. 				for j in range(0,n):
  27. 					if (k):
  28. 						D[k][i][j]=min(D[k-1][i][j],D[k-1][i][k]+D[k-1][k][j])
  29. 						if D[k][i][j]== (D[k-1][i][k]+D[k-1][k][j]) : p[k][i][j]=p[k-1][k][j]
  30. 						else:	p[k][i][j]=p[k-1][i][j]
  31.  
  32. 					else:
  33. 						D[0][i][j]=min(D0[i][j],D0[i][0]+D0[0][j])
  34. 						if D[0][i][j]==(D0[i][0]+D0[0][j]) : p[0][i][j]=p0[0][j] 
  35. 						else:	p[0][i][j]=p0[i][j]
  36. 		print(p0)
  37. 		return D[n-1],p0
  38. edge={(0,1):6,(0,2):-1,(1,0):2,(1,2):2,(2,1):3}
  39. graph={0:[1,2],1:[0,2],2:[1]}
  40. G=Graph(graph,edge)
  41. G.Floyd_Warshall()# your code goes here
Success #stdin #stdout 0s 23352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[None, 0, 0], [1, None, 1], [None, 2, None]]
[[None, None, None], [None, None, None], [None, None, None]]
https://ideone.com/8kOQIJ
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!