shortest_path.py

"""
Shortest path algorithms for all pairs
"""
MAX = 134901347088


import numpy
def read_graph(fname):
    G = []
	with open(fname) as fp:
		V, E = [int(el) for el in fp.readline().split(" ")]
		G = [[] for i in range(V)]    
		for line in fp:
			u, v, length = [int(el) for el in line.split(" ")]
			G[v - 1].append((u - 1, length))
	return G

def floyd(G):
	n = len(G)
	
	# initialize
	A = numpy.zeros((n, n, 2))
	A.fill(MAX)
	for i in range(n):
		A[i][i][0] = 0
		for k, c in G[i]:
			A[k][i][0] = c
	prev, cur = 0, 1
	for k in range(1, n):
		for i in range(n):
			for j in range(n):
				A[i][j][cur] = min(A[i][j][prev], A[i][k][prev]+A[k][j][prev])
		prev, cur = cur, prev
	has_negative = any((A[i][i][cur] < 0) for i in range(n))
	if has_negative:
		return None
	return min(A[i][j][cur] for i in range(n) for j in range(n))
			


# dijkstraData.txt
def dikstra(G, s):
	MAX_VAL = MAX
	visited = set([s])
	frontier = set([])
	A = [MAX_VAL for i in range(len(G))]
	A[s]=0
	
	for v, length in G[s]:
		frontier.add(v)
		A[v] = length
	# initialise shortest paths
	
	while len(visited)!=len(G) and frontier:
		length, end = min([(A[el],el) for el in frontier])
		#print "========="
		#print "Choose node %s" %(end)
		#print "visited %s" %(visited)
		#print "frontier %s" %frontier
		#print " neihbours %s" %G[end] 
		visited.add(end)
		frontier.remove(end)
		for v, lenv in G[end]:
			if v not in visited:
	#			print "Updating node %s: from %s to %s" %(v, A[v], min(A[v], A[end]+lenv)) 
				A[v] = min(A[v], A[end]+lenv)
				frontier.add(v)
	return A
	
	
	
def bellman_ford(G, s):
	"""
	
	Calculates the lenghts of the shortest paths to all vertexes
	from s
	Returns the shortest path lenghts
	"""
	n = len(G)
	print n, s
	A = [[MAX]*n, [MAX]*n]
	A[0][s] = 0
	cur , prev = 1, 0
	for i in range(n + 1):
		for v in range(n):
			A[cur][v] = min(A[prev][v], min([A[prev][u] + c for u, c in G[v]] + [MAX]))
		cur, prev = prev, cur
	for i in range(n):
		if A[cur][i] != A[prev][i]:
			return None
	return A[cur]
import copy
def johnson(G):
	n = len(G)
	G_extended = copy.deepcopy(G)
	for i in range(n):
		# append to all lists the new vertex n with edge lenght 0
		G_extended[i].append((n , 0))
	G_extended.append([]) 
	
	weight_displayments = bellman_ford(G_extended, n)
	
	if not weight_displayments:
		# graph has negative cyrcles
		return None
	P = weight_displayments
	G_positive = copy.deepcopy(G)
	for v in range(n):
		for i in range(len(G[v])):
			u, c = G_positive[v][i]
			G_positive[v][i]  = (u, c + P[u] - P[v])
	ss = MAX
	for v in range(n):
		print "dikjstra %d" % v
		# calc all min paths from v
		vminPaths = dikstra(G_positive, v)
		vminPaths = [vminPaths[i] - P[v] + P[i] for i in range(len(vminPaths))]
		
		# keep only min
		ss = min(min(vminPaths), ss)
	return ss



G = read_graph("g3.txt")
# print floyd(G) # toooo slow

print johnson(G)