Instantly share code, notes, and snippets.

Embed
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
@vincentarelbundock

This comment has been minimized.

vincentarelbundock commented Dec 4, 2013

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

@dlumma

This comment has been minimized.

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

This comment has been minimized.

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

This comment has been minimized.

rahanar commented Apr 3, 2014

@benaxelrod

This comment has been minimized.

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

This comment has been minimized.

bizzk3t commented Jun 23, 2014

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

@joyrexus

This comment has been minimized.

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

This comment has been minimized.

57uff3r commented Oct 13, 2014

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

@ross-kruse

This comment has been minimized.

ross-kruse commented Apr 11, 2015

How do I interpret the output?

@mdsrosa

This comment has been minimized.

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

This comment has been minimized.

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

This comment has been minimized.

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?

@TejazTj

This comment has been minimized.

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

@KanwarGill

This comment has been minimized.

KanwarGill commented Feb 8, 2016

This was very useful. Thank you!

@jzohrab

This comment has been minimized.

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

This comment has been minimized.

MagallanesFito commented Jun 12, 2016

Nice code, clear and great. Thank you

@MagallanesFito

This comment has been minimized.

MagallanesFito commented Jun 12, 2016

Nice code, clear and great. Thank you

@jazcap53

This comment has been minimized.

jazcap53 commented Jun 29, 2016

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

@rockyzhengwu

This comment has been minimized.

rockyzhengwu commented Aug 6, 2016

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

@freegyp

This comment has been minimized.

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).

@alexhwoods

This comment has been minimized.

alexhwoods commented Sep 26, 2016

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

Great implementation!

@arganoid

This comment has been minimized.

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

This comment has been minimized.

zirons1 commented Dec 6, 2016

You spelled Dijkstra wrong in the function definition -_-

@eyzuky

This comment has been minimized.

eyzuky commented Dec 17, 2016

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

@manliu1225

This comment has been minimized.

manliu1225 commented Feb 17, 2017

thank you. this is very useful for me.

@maskani-moh

This comment has been minimized.

maskani-moh commented Feb 20, 2017

Great code. Thank you!

@elvaigh

This comment has been minimized.

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

This comment has been minimized.

kyle-sorensen commented Mar 16, 2017

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

from collections import defaultdict

@danielgaza

This comment has been minimized.

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:

  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

This comment has been minimized.

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

This comment has been minimized.

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

@manoelstilpen

This comment has been minimized.

manoelstilpen commented Jun 9, 2017

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

@abelevtsov

This comment has been minimized.

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

This comment has been minimized.

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

This comment has been minimized.

tatianass commented Dec 14, 2017

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

@MaximusWudy

This comment has been minimized.

MaximusWudy commented Jan 13, 2018

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.nodes.add(i) # add element into set
    
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)])
g.add_edge(1, 2, 4)
g.add_edge(1, 3, 1)
g.add_edge(2, 4, 3)
g.add_edge(2, 5, 7)
g.add_edge(4, 8, 3)
g.add_edge(5, 8, 4)
g.add_edge(3, 6, 3)
g.add_edge(3, 7, 2)
g.add_edge(6, 7, 1)
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})

@bp8017

This comment has been minimized.

bp8017 commented Feb 3, 2018

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

@agbenn

This comment has been minimized.

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

This comment has been minimized.

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

This comment has been minimized.

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

This comment has been minimized.

felipedelosh commented May 15, 2018

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

This comment has been minimized.

betandr commented Jul 16, 2018

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

This comment has been minimized.

mlhtnc commented Oct 20, 2018

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

@AlkisPis

This comment has been minimized.

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?

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