PandaWhoCodes · October 26, 2019 14:13 · Dec 15, 2015 · Dec 15, 2015
diff --git a/dijkstra.py b/dijkstra.py
@@ -1,2 +1,60 @@
 # Zaz Brown
-# An efficient algorithm to find shortest paths between nodes in a graph.
+# github.com/zaz/dijkstra
+"""An efficient algorithm to find shortest paths between nodes in a graph."""
+from collections import defaultdict
+
+class Digraph(object):
+    def __init__(self, nodes=[]):
+        self.nodes = set()
+        self.neighbours = defaultdict(set)
+        self.dist = {}
+
+    def addNode(self, *nodes):
+        [self.nodes.add(n) for n in nodes]
+
+    def addEdge(self, frm, to, d=1e309):
+        self.addNode(frm, to)
+        self.neighbours[frm].add(to)
+        self.dist[ frm, to ] = d
+
+    def dijkstra(self, start, maxD=1e309):
+        """Returns a map of nodes to distance from start and a map of nodes to
+        the neighbouring node that is closest to start."""
+        # total distance from origin
+        tdist = defaultdict(lambda: 1e309)
+        tdist[start] = 0
+        # neighbour that is nearest to the origin
+        preceding_node = {}
+        unvisited = self.nodes
+
+        while unvisited:
+            current = unvisited.intersection(tdist.keys())
+            if not current: break
+            min_node = min(current, key=tdist.get)
+            unvisited.remove(min_node)
+
+            for neighbour in self.neighbours[min_node]:
+                d = tdist[min_node] + self.dist[min_node, neighbour]
+                if tdist[neighbour] > d and maxD >= d:
+                    tdist[neighbour] = d
+                    preceding_node[neighbour] = min_node
+
+        return tdist, preceding_node
+
+    def min_path(self, start, end, maxD=1e309):
+        """Returns the minimum distance and path from start to end."""
+        tdist, preceding_node = self.dijkstra(start, maxD)
+        dist = tdist[end]
+        backpath = [end]
+        try:
+            while end != start:
+                end = preceding_node[end]
+                backpath.append(end)
+            path = list(reversed(backpath))
+        except KeyError:
+            path = None
+
+        return dist, path
+
+    def dist_to(self, *args): return self.min_path(*args)[0]
+    def path_to(self, *args): return self.min_path(*args)[1]
diff --git a/dijkstra.py b/dijkstra.py
@@ -0,0 +1,2 @@
+# Zaz Brown
+# An efficient algorithm to find shortest paths between nodes in a graph.
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,2 @@
		# Zaz Brown
		# An efficient algorithm to find shortest paths between nodes in a graph.
No results found