sawine@2: """
sawine@2: Name: dijkstra - Dijkstra for the Single Source Shortest Path problem
sawine@2: 
sawine@2: Description: dijkstra applies the Dijkstra algorithm for the Single Source Shortest Path problem.
sawine@2: 
sawine@2: Author: Eugen Sawin <sawine@me73.com>
sawine@2: """
sawine@2: 
sawine@2: def main():
sawine@2:     args = parse_arguments()
sawine@2:     s = args.source
sawine@2:     raw_graph = args.graph
sawine@2:     graph = [e.strip(' ,(').split(',') for e in raw_graph.split(')')]
sawine@2:     graph = [(e[0].strip(), e[1].strip(), int(e[2].strip())) for e in graph if len(e) == 3]
sawine@2:     distances = dijkstra(s, create_graph(graph))
sawine@2:     for (v, d) in distances.iteritems():
sawine@2:         print '%s: %i' % (v, d)
sawine@2: 
sawine@2: def create_graph(desc):
sawine@2:     vertices = set([e[0] for e in desc]) 
sawine@2:     vertices = vertices.union([e[1] for e in desc])
sawine@2:     edges = dict(zip([(v1, v2) for (v1, v2, _) in desc], [c for (_, _, c) in desc]))
sawine@2:     return (vertices, edges)    
sawine@2: 
sawine@2: from heapq import *
sawine@2: 
sawine@2: def dijkstra(s, (vertices, edges)):
sawine@2:     inf = sum(edges.itervalues()) + 1
sawine@2:     dist = dict([(v, inf) for v in vertices])
sawine@2:     dist[s] = 0
sawine@2:     u = []
sawine@2:     for (v, d) in dist.iteritems():
sawine@2:         heappush(u, (d, v))
sawine@2:     active = vertices
sawine@2:     while len(u) and len(active):
sawine@2:         (_, node) = heappop(u)
sawine@2:         if node in active:
sawine@2:             active.remove(node)
sawine@2:             for (v1, v2) in [e for e in edges.iterkeys() if e[0] == node]:
sawine@2:                 c = edges[(v1, v2)]
sawine@2:                 if dist[v2] > dist[v1] + c:
sawine@2:                     dist[v2] = dist[v1] + c
sawine@2:                     heappush(u, (dist[v2], v2))
sawine@2:     return dist                    
sawine@2: 
sawine@2: from argparse import ArgumentParser
sawine@2: 
sawine@2: def parse_arguments():
sawine@2:     parser = ArgumentParser(description='Applies the Dijkstra algorithm for the single source shortest path problem.')
sawine@2:     parser.add_argument('graph', help='sequence of (u, v, c(u,v))')
sawine@2:     parser.add_argument('source', help='source vertex')
sawine@2:     return parser.parse_args()
sawine@2: 
sawine@2: if __name__ == "__main__":
sawine@2:     main()