{{ message }}

Instantly share code, notes, and snippets.

# zaz/dijkstra.py

Last active Nov 23, 2020
Dijkstra's algorithm — Python
 # Zaz Brown # 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) def path_to(self, *args): return self.min_path(*args)

### christopher-abastar commented Feb 2, 2017

 Hi, i have these sample datasets. Seems to be not working from F to E. ```def main(): graph = Digraph(nodes = ['A','B','C','D','E','F','G']) graph.add_edge("A", "B", 7) graph.add_edge("A", "D", 5) graph.add_edge("B", "C", 8) graph.add_edge("B", "D", 9) graph.add_edge("B", "E", 7) graph.add_edge("C", "E", 5) graph.add_edge("D", "E", 15) graph.add_edge("D", "F", 6) graph.add_edge("E", "F", 8) graph.add_edge("E", "G", 9) graph.add_edge("F", "G", 11) print(graph.min_path("A","D")) print(graph.min_path("A","E")) print(graph.min_path("F","G")) print(graph.min_path("F","E")) if __name__ == "__main__": main()```

### PDelerm commented Feb 15, 2017 • edited

I got this error :

## Estimation du Traffic dans les réseaux optiques multi-débit

Entrez la Source : 1
Entrez la Destination : 14
Traceback (most recent call last):
File "NET.py", line 100, in
print(graph.min_path(source, destination))
NameError: name 'graph' is not defined

### ctriley commented Jul 10, 2017 • edited

 I may be doing something wrong, but I believe this code will not work for multiple calls of dijkstra's algorithm. It seems to remove all of the nodes from the graph every time this algorithm is called. `unvisited = self.nodes` and then `unvisited.remove(min_node)`. To fix this I changed line 28 to `unvisited = copy.copy(self.nodes)`

### khairakiran6 commented Sep 6, 2020

 Can u help how to take input from a file . like a/ b/ 8 is format from node a to b distance is 8