{{ message }}

Instantly share code, notes, and snippets.

# econchick/gist:4666413

Last active Sep 9, 2020
Python implementation of Dijkstra's Algorithm
 class Graph: def __init__(self): self.nodes = set() self.edges = defaultdict(list) self.distances = {} def add_node(self, value): self.nodes.add(value) def add_edge(self, from_node, to_node, distance): self.edges[from_node].append(to_node) self.edges[to_node].append(from_node) self.distances[(from_node, to_node)] = distance def dijsktra(graph, initial): visited = {initial: 0} path = {} nodes = set(graph.nodes) while nodes: min_node = None for node in nodes: if node in visited: if min_node is None: min_node = node elif visited[node] < visited[min_node]: min_node = node if min_node is None: break nodes.remove(min_node) current_weight = visited[min_node] for edge in graph.edges[min_node]: weight = current_weight + graph.distance[(min_node, edge)] if edge not in visited or weight < visited[edge]: visited[edge] = weight path[edge] = min_node return visited, path

### vincentarelbundock commented Dec 4, 2013

 I was looking for this. Thanks! Very nice nice and clean!

### dlumma commented Feb 27, 2014

 Thanks for this! I tried running it and ran into a typo. Line 38: typo in distance should be distances

### shahkomal commented Mar 20, 2014

 I am not able to understand what to pass in the second argument (initial) for dijsktra function. Can anyone please help me?

### rahanar commented Apr 3, 2014

 you need to pass the start node. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Algorithm

### benaxelrod commented Jun 9, 2014

 I think you also need: `````` self.distances[(to_node, from_node)] = distance `````` at line 14. Or else the algorithm won't know the distance from nodes A to B is the same as from B to A.

### bizzk3t commented Jun 23, 2014

 benaxelrod, I believe if you add that line, it will make the graph undirected rather than directed

### joyrexus commented Jun 28, 2014

 Note the running time for this implementation is going to be O(mn) where n is the number of vertices and m is the number of edges. FWIW, implementations that utilize a priority queue can run in O(m log n) time.

### 57uff3r commented Oct 13, 2014

 I also added try-catch block in loop with edges: https://gist.github.com/57uff3r/99b4064cbbcbf6a73963

### ross-kruse commented Apr 11, 2015

 How do I interpret the output?

### mdsrosa commented Nov 21, 2015

 @econchick Thank you very much for sharing this implementation. 😄 @rokruse I've added a function that shows that result in a very nice way to interpret it: https://gist.github.com/mdsrosa/c71339cb23bc51e711d8

### zaz commented Dec 15, 2015

 A lot of the first half of the loop can be cleaned up using `set.intersection()` and `min()`. It also seems like you could do with some functions to actually find the path: zaz / dijkstra.py

### SHIMONSHEIBA commented Dec 25, 2015

 @econchick Could I modify this implementation to a DIRECTED graph by deleting row 12: self.edges[to_node].append(from_node) Will it work? @joyrexus could you please give another link that works?

### KanwarGill commented Feb 8, 2016

 This was very useful. Thank you!

### jzohrab commented Mar 31, 2016

 I don't believe the gist's implementation is correct, at least it doesn't work on a simple use case unless I've misused it. I have a simple ring, `a -> b, a -> c, b -> c` with weights. The algorithm doesn't give distances to b or c, even with the try-catch block from 57uff3r. ``````import dj g = dj.Graph() g.add_node('a') g.add_node('b') g.add_node('c') g.add_edge('a', 'b', 10) g.add_edge('b', 'c', 10) g.add_edge('a', 'c', 15) print dj.dijsktra(g, 'a') # returns ({'a': 0}, {}) ``````

### MagallanesFito commented Jun 12, 2016

 Nice code, clear and great. Thank you

### MagallanesFito commented Jun 12, 2016

 Nice code, clear and great. Thank you

### jazcap53 commented Jun 29, 2016

 Thanks very much for this. Clean, clear -- taught me a lot!

### rockyzhengwu commented Aug 6, 2016

 delete self.edges[to_node].append(from_node) row 12 because the graph directed.

### freegyp commented Sep 10, 2016 • edited

 If I'm right, in this implementation, finding min_node takes O(n) time (n is the number of nodes).

### alexhwoods commented Sep 26, 2016

 Agree with rockyzhengwu, it's a directed, weighted graph. Great implementation!

### arganoid commented Nov 16, 2016 • edited

 ` g = Graph() g.add_node('a') g.add_node('b') g.add_node('c') g.add_node('d') g.add_edge('a', 'b', 10) g.add_edge('b', 'c', 10) g.add_edge('a', 'c', 15) g.add_edge('c', 'd', 20) print(dijsktra(g, 'a')) ` Output is: `({'a': 0, 'c': 15, 'b': 10}, {'c': 'a', 'b': 'a'})` What happened to d?

### zirons1 commented Dec 6, 2016

 You spelled Dijkstra wrong in the function definition -_-

### eyzuky commented Dec 17, 2016

 I have a silly question - where do I specify my target node?

### manliu1225 commented Feb 17, 2017

 thank you. this is very useful for me.

### maskani-moh commented Feb 20, 2017

 Great code. Thank you!

### elvaigh commented Mar 4, 2017

 few mistake in line 38 : "weight = current_weight + graph.distance[(min_node, edge)] " ==> weight = current_weight + graph.distances[(min_node, edge)] Thanks very usefull!

### ghost commented Mar 16, 2017

 I can't speak for Python 3 but in 2.7 you need: `from collections import defaultdict `

### danielgaza commented May 2, 2017

 Hello Dears I have a question regarding the short path Dijkstra, I read the algorithm, but I do not know how to apply it on my graph. I have a graph network composed of 11 points, and the points coordinates are as follow: A(2,9) B(1,6) C(5,3) D(4,7) E(6,8) F(6,6) G(8,5) H(12,4) I(12,7) J(10,9) K(8,7) and the points are connected together by 23 lines as follow: AB BC BD AD DC AE DE DF CF EF CG FG FK EK KG CH GH GI KI IH EJ KJ IJ How I can find the shortest path between point A and point H using the above explained defined function ? Please help me. Thanks in advance

### ngocqd commented May 15, 2017

 when i run code in pycharm, i got the error TypeError: '<' not supported between instances of 'Vertex' and 'Vertex'

### Rajdeep400 commented May 31, 2017 • edited

 with due respect to econchick, thanks to your submitted code, but people you can use this code of mine, I just simply fixed some bugs of the code above, and also path is displayed here; it is also a directed graph, NO ERROR. All credit to econchick. Fixed by : ME from collections import defaultdict class Graph: def init(self): self.nodes = set() self.edges = defaultdict(list) self.distances = {} ``````def add_node(self, value): self.nodes.add(value) def add_edge(self, from_node, to_node, distance): self.edges[from_node].append(to_node) self.distances[(from_node, to_node)] = distance `````` def dijkstra(graph, initial): visited = {initial: 0} path = defaultdict(list) ``````nodes = set(graph.nodes) while nodes: min_node = None for node in nodes: if node in visited: if min_node is None: min_node = node elif visited[node] < visited[min_node]: min_node = node if min_node is None: break nodes.remove(min_node) current_weight = visited[min_node] for edge in graph.edges[min_node]: weight = current_weight + graph.distances[(min_node, edge)] if edge not in visited or weight < visited[edge]: visited[edge] = weight path[edge].append(min_node) return path `````` g = Graph() g.add_node('A') g.add_node('B') g.add_node('C') g.add_node('D') g.add_node('E') g.add_node('F') g.add_node('G') g.add_edge('A','B',12) g.add_edge('A','C',7) g.add_edge('B','D',1) g.add_edge('B','A',12) g.add_edge('D','E',8) g.add_edge('C','F',3) g.add_edge('D','G',5) g.add_edge('F','B',1) g.add_edge('F','G',2) g.add_edge('C','D',13) g.add_edge('E','B',6) print(dijkstra(g, 'A')['B'])

### manoelstilpen commented Jun 9, 2017

 You should add in the function `add_edge` the command `self.distances[(to_node, from_node)] = distance`

### abelevtsov commented Jul 15, 2017

 please fix `weight = current_weight + graph.distance[(min_node, edge)]` to `weight = current_weight + graph.distances[(min_node, edge)]` (distance -> distances)

### esarabdikar commented Aug 3, 2017

 hey, can I implement this dijkstra code on mobile robot ? I use simulator mobile robot "pysimiam" which is python version of matlab's sim.i.am.

### tatianass commented Dec 14, 2017

 It doesn't work when the destination is the same as the origin.

### MaximusWudy commented Jan 13, 2018 • edited

Here is a complete version of Python2.7 code regarding the problematic original version. Just paste in in any .py file and run.
Output: The storage objects are pretty clear; dijkstra algorithm returns with first dict of shortest distance from source_node to {target_node: distance length} and second dict of the predecessor of each node, i.e. {2:1} means the predecessor for node 2 is 1 --> we then are able to reverse the process and obtain the path from source node to every other node.

For example, we have {5:2} and {2:1}, which renders that the path from source node 1 to 5 is 1-->2-->5.

from collections import defaultdict
class Graph:
def init(self):
self.nodes = set() # set object
self.edges = defaultdict(list)
self.distances = {}

``````def add_nodes(self, value):
for i in value:

self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node) # dict to neighbour nodes
self.distances[(from_node, to_node)] = distance # dict for distance
self.distances[(to_node, from_node)] = distance
``````

def dijsktra(graph, initial):
visited = {initial: 0}
path = {}

``````nodes = set(graph.nodes)

while nodes:
min_node = None
for node in nodes:
if node in visited:
if min_node is None:
min_node = node
elif visited[node] < visited[min_node]:
min_node = node

if min_node is None:
break

nodes.remove(min_node)
current_weight = visited[min_node]

for edge in graph.edges[min_node]:
weight = current_weight + graph.distances[(min_node, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node

return visited, path
``````

g = Graph()
print "nodes:", g.nodes
print "edges:", g.edges
print "distances: ", g.distances

# ----------

print "-" * 25
source_node = 1
print "Source node:", source_node
print dijsktra(g, 1) # return with visited and path

## And the return output should be : nodes: set([1, 2, 3, 4, 5, 6, 7, 8]) edges: defaultdict(<type 'list'>, {1: [2, 3], 2: [1, 4, 5], 3: [1, 6, 7], 4: [2, 8], 5: [2, 8], 6: [3, 7], 7: [3, 6], 8: [4, 5]}) distances: {(1, 2): 4, (7, 3): 2, (1, 3): 1, (6, 7): 1, (4, 8): 3, (8, 5): 4, (7, 6): 1, (3, 1): 1, (2, 1): 4, (6, 3): 3, (3, 6): 3, (3, 7): 2, (4, 2): 3, (2, 5): 7, (5, 2): 7, (2, 4): 3, (5, 8): 4, (8, 4): 3}

Source node: 1
({1: 0, 2: 4, 3: 1, 4: 7, 5: 11, 6: 4, 7: 3, 8: 10}, {2: 1, 3: 1, 4: 2, 5: 2, 6: 3, 7: 3, 8: 4})

### brett-petrusek commented Feb 3, 2018

 I am looking for an "opposite" of this. Something that finds the longest path between vertices.

### agbenn commented Feb 11, 2018

 Should you also have a line like this in the code below line 13? : self.distances[(to_node, from_node)] = distance

### Iambecomeroot commented Mar 26, 2018

 @joyrexus your link is broken. Do you have a current link to an algorithm with O(m log n)?

### samnoonan88 commented Apr 19, 2018

 This looks great, thank you. Can anyone tell me how to pass the values and get it to work? I'd like to demonstrate this to a class and am unsure on how to do this. Any comments or examples would be much appreciated.

### felipedelosh commented May 15, 2018 • edited

 all right but i watch a error in incomplete graph. g = Graph() g.add_node('x') g.add_node('y') g.add_node('z') g.add_edge('x', 'y', 100) g.add_edge('y', 'z', 90) g.add_edge('z', 'x', 78) print(dijsktra(g, 'x')) .... error weight = current_weight + graph.distances[(min_node, edge)] KeyError: ('x', 'z') not exist conection to x::z i change this lines ``````for edge in graph.edges[min_node]: try: weight = current_weight + graph.distances[(min_node, edge)] except: weight = current_weight + math.inf if edge not in visited or weight < visited[edge]: visited[edge] = weight path[edge] = min_node ``````

### betandr commented Jul 16, 2018 • edited

 I implemented it here as: ``````def dijkstra(graph, source): q = set() dist = {} prev = {} for v in graph.nodes: # initialization dist[v] = INFINITY # unknown distance from source to v prev[v] = INFINITY # previous node in optimal path from source q.add(v) # all nodes initially in q (unvisited nodes) # distance from source to source dist[source] = 0 while q: # node with the least distance selected first u = min_dist(q, dist) q.remove(u) if u.label in graph.edges: for _, v in graph.edges[u.label].items(): alt = dist[u] + v.length if alt < dist[v.to_node]: # a shorter path to v has been found dist[v.to_node] = alt prev[v.to_node] = u return dist, prev `````` ...with the objects: ``````class Node: def __init__(self, label): self.label = label `````` ``````class Edge: def __init__(self, to_node, length): self.to_node = to_node self.length = length `````` ``````class Graph: def __init__(self): self.nodes = set() self.edges = dict() def add_node(self, node): self.nodes.add(node) def add_edge(self, from_node, to_node, length): edge = Edge(to_node, length) if from_node.label in self.edges: from_node_edges = self.edges[from_node.label] else: self.edges[from_node.label] = dict() from_node_edges = self.edges[from_node.label] from_node_edges[to_node.label] = edge ``````

### mlhtnc commented Oct 20, 2018

 There is a typo here "def dijsktra(graph, initial):". It would be better to change it as dijkstra.

### AlkisPis commented Dec 11, 2018

 I envy all the people here who can work on this code with no no problem and even if important info is missing! Well, 1) I miss info on where is 'graph' defined (or at least how to create one) and 2) I get "NameError: global name 'defaultdict' is not defined". Any ideas?

### JeevaTM commented Feb 18, 2019 • edited

 @AlkisPis, `from collections import defaultdict` to clear that error

### AlkisPis commented May 26, 2019

 @JeevaTM, Thanks. You are really very fast ... You replied on Feb 18 to a question I posted on Dec 18! :)) Well, except if you can see the future! :)

### nolfonzo commented Jun 18, 2019

 This follows the wikipedia definition closely: http://rebrained.com/?p=392 import sys def shortestpath(graph,start,end,visited=[],distances={},predecessors={}): """Find the shortest path btw start & end nodes in a graph""" ``````# detect if first time through, set current distance to zero if not visited: distances[start]=0 # if we've found our end node, find the path to it, and return if start==end: path=[] while end != None: path.append(end) end=predecessors.get(end,None) return distances[start], path[::-1] # process neighbors as per algorithm, keep track of predecessors for neighbor in graph[start]: if neighbor not in visited: neighbordist = distances.get(neighbor,sys.maxint) tentativedist = distances[start] + graph[start][neighbor] if tentativedist < neighbordist: distances[neighbor] = tentativedist predecessors[neighbor]=start # neighbors processed, now mark the current node as visited visited.append(start) # finds the closest unvisited node to the start unvisiteds = dict((k, distances.get(k,sys.maxint)) for k in graph if k not in visited) closestnode = min(unvisiteds, key=unvisiteds.get) # now take the closest node and recurse, making it current return shortestpath(graph,closestnode,end,visited,distances,predecessors) `````` if name == "main": graph = {'a': {'w': 14, 'x': 7, 'y': 9}, 'b': {'w': 9, 'z': 6}, 'w': {'a': 14, 'b': 9, 'y': 2}, 'x': {'a': 7, 'y': 10, 'z': 15}, 'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11}, 'z': {'b': 6, 'x': 15, 'y': 11}} print shortestpath(graph,'a','a') print shortestpath(graph,'a','b') ``````""" Expected Result: (0, ['a']) (20, ['a', 'y', 'w', 'b']) """ ``````

### drocpdp commented Apr 10, 2020

 I think you also need: `````` self.distances[(to_node, from_node)] = distance `````` at line 14. Or else the algorithm won't know the distance from nodes A to B is the same as from B to A. I think it's possible B to A is not the same as A to B. (For example, in a representation of a road network, a 1-way road). I think the user is responsible for adding B to A with the same distance in the usage of add_edge(). You can implement validation/setting that B to A is == A to B, but it would restrict your implementation to solely equidistant and single edge graphs. Would you agree?