Skip to content

Instantly share code, notes, and snippets.

@econchick
Last active December 22, 2023 13:32
Show Gist options
  • Save econchick/4666413 to your computer and use it in GitHub Desktop.
Save econchick/4666413 to your computer and use it in GitHub Desktop.
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
@abelevtsov
Copy link

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

@esarabdikar
Copy link

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
Copy link

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

@MaximusWudy
Copy link

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

@brett-petrusek
Copy link

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

@agbenn
Copy link

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
Copy link

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

@samnoonan88
Copy link

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
Copy link

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
Copy link

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
Copy link

mlhtnc commented Oct 20, 2018

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

@AlkisPis
Copy link

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
Copy link

JeevaTM commented Feb 18, 2019

@AlkisPis, from collections import defaultdict to clear that error

@AlkisPis
Copy link

@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
Copy link

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
Copy link

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
Copy link

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

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