def floyd_warshall(graph):
	"""
	All Pairs Shortest Path problem. 
	The problem is to find shortest distances between every 
	pair of vertices in a given edge weighted directed Graph
	"""
	n = len(graph[0])

	dist = [ [0]*n for i in range(n) ]

	# Initialize the solution matrix same as input graph matrix
	for i in range(n):
		for j in range(n):
			dist[i][j] = graph[i][j]

	for k in range(n):
		for i in range(n):
			for j in range(n):
				if dist[i][k] + dist[k][j] < dist[i][j]:
					dist[i][j] = dist[i][k] + dist[k][j]

	return dist