dijkstra's shortest path.

dijkstra.py

#!/usr/bin/env python

import sys
from altgraph import Graph


def read_graph(f):
	g = Graph.Graph()
	for l in file(f):
		l = l.rstrip().split()
		# read vertex
		v = int(l[0])
		l.pop(0)

		# read neighbor & length
		for i in l:
			i = i.split(',')
			g.add_edge(v, int(i[0]), int(i[1]))

	return g


def dijkstra(graph, start):
	dist = {}
	for v in graph.nodes:
		dist[v] = sys.maxint

	prev = {}
	for v in graph.nodes:
		prev[v] = None

	dist[start] = 0
	Q = graph.nodes.copy()

	while len(Q):
		# find vertex with smallest distance.
		min_dist = sys.maxint
		u = Q.keys()[0] # first vertex
		for v in Q:
			if dist[v] < min_dist:
				u = v
				min_dist = dist[v]

		del(Q[u])
		if dist[u] == sys.maxint:
			break

		# find neighbors
		neighbors = {}
		for e in graph.edges.values():
			if e[0] == u:
				neighbors[e[1]] = e[2]

		for v in neighbors:
			alt = dist[u] + neighbors[v]
			if alt < dist[v]:
				dist[v], prev[v] = alt, u
	return dist, prev


if __name__=='__main__':
	if len(sys.argv) > 2:
		graph_file = sys.argv[1]
		start = int(sys.argv[2])
		end = int(sys.argv[3])

		g = read_graph(graph_file)
		dis = dijkstra(g, start)
		print dis[0][end]