Instantly share code, notes, and snippets.

# econchick/gist:4666413

Last active November 15, 2022 06:49
Python implementation of Dijkstra's Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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

### 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()

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:

1. AB
2. BC
3. BD
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 ?

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

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

`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

### MarcelRobitaille 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()

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

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?

### ankur619158 commented Dec 8, 2020

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

it is the starting node which has no parent that's why 0