Instantly share code, notes, and snippets. econchick/gist:4666413 Last active Oct 13, 2019

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!

kyle-sorensen 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'

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 = {}

for i in value:

def add_edge(self, from_node, to_node, distance):
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()
g.add_nodes([i+1 for i in range(8)])
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']) """
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.