Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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

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

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

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

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

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

@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?

TejazTj commented Feb 7, 2016

but i have a different code...can u help me solve it..??

screen shot 2016-02-07 at 2 47 33 pm
screen shot 2016-02-07 at 2 47 52 pm
screen shot 2016-02-07 at 2 48 07 pm

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}, {})

Nice code, clear and great. Thank you

Nice code, clear and great. Thank you

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

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

freegyp commented Sep 10, 2016

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

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

Great implementation!

arganoid commented Nov 16, 2016

`
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?

thank you. this is very useful for me.

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!

I can't speak for Python 3 but in 2.7 you need:

from collections import defaultdict

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:

  1. AB
  2. BC
  3. BD
  4. AD
  5. DC
  6. AE
  7. DE
  8. DF
  9. CF
  10. EF
  11. CG
  12. FG
  13. FK
  14. EK
  15. KG
  16. CH
  17. GH
  18. GI
  19. KI
  20. IH
  21. EJ
  22. KJ
  23. 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

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'])

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

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

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment