Added (DP) Fibonacci example.
2 Name: dijkstra - Dijkstra for the Single Source Shortest Path problem
4 Description: dijkstra applies the Dijkstra algorithm for the Single Source Shortest Path problem.
6 Author: Eugen Sawin <sawine@me73.com>
10 args = parse_arguments()
12 raw_graph = args.graph
13 graph = [e.strip(' ,(').split(',') for e in raw_graph.split(')')]
14 graph = [(e[0].strip(), e[1].strip(), int(e[2].strip())) for e in graph if len(e) == 3]
15 distances = dijkstra(s, create_graph(graph))
16 for (v, d) in distances.iteritems():
17 print '%s: %i' % (v, d)
19 def create_graph(desc):
20 vertices = set([e[0] for e in desc])
21 vertices = vertices.union([e[1] for e in desc])
22 edges = dict(zip([(v1, v2) for (v1, v2, _) in desc], [c for (_, _, c) in desc]))
23 return (vertices, edges)
27 def dijkstra(s, (vertices, edges)):
28 inf = sum(edges.itervalues()) + 1
29 dist = dict([(v, inf) for v in vertices])
32 for (v, d) in dist.iteritems():
35 while len(u) and len(active):
36 (_, node) = heappop(u)
39 for (v1, v2) in [e for e in edges.iterkeys() if e[0] == node]:
41 if dist[v2] > dist[v1] + c:
42 dist[v2] = dist[v1] + c
43 heappush(u, (dist[v2], v2))
46 from argparse import ArgumentParser
48 def parse_arguments():
49 parser = ArgumentParser(description='Applies the Dijkstra algorithm for the single source shortest path problem.')
50 parser.add_argument('graph', help='sequence of (u, v, c(u,v))')
51 parser.add_argument('source', help='source vertex')
52 return parser.parse_args()
54 if __name__ == "__main__":