Instantly share code, notes, and snippets.

# kachayev/dijkstra.py

Last active April 14, 2024 06:58
Show Gist options
• Save kachayev/5990802 to your computer and use it in GitHub Desktop.
Dijkstra shortest path algorithm based on python heapq heap implementation
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
 from collections import defaultdict from heapq import * def dijkstra(edges, f, t): g = defaultdict(list) for l,r,c in edges: g[l].append((c,r)) q, seen, mins = [(0,f,())], set(), {f: 0} while q: (cost,v1,path) = heappop(q) if v1 not in seen: seen.add(v1) path = (v1, path) if v1 == t: return (cost, path) for c, v2 in g.get(v1, ()): if v2 in seen: continue prev = mins.get(v2, None) next = cost + c if prev is None or next < prev: mins[v2] = next heappush(q, (next, v2, path)) return float("inf"), None if __name__ == "__main__": edges = [ ("A", "B", 7), ("A", "D", 5), ("B", "C", 8), ("B", "D", 9), ("B", "E", 7), ("C", "E", 5), ("D", "E", 15), ("D", "F", 6), ("E", "F", 8), ("E", "G", 9), ("F", "G", 11) ] print "=== Dijkstra ===" print edges print "A -> E:" print dijkstra(edges, "A", "E") print "F -> G:" print dijkstra(edges, "F", "G")

### kevthanewversi commented Sep 24, 2018

this is brilliant. Thanks @kachayev

### u2takey commented Nov 13, 2018 • edited

seen is redundant

```def dijkstra(edges, f, t):
g = defaultdict(list)
for l,r,c in edges:
g[l].append((c,r))

q, dist = [(0,f,())], {f: 0}
while q:
(cost, node, path) = heappop(q)
if cost > dist[node]: continue
path += (node, )
if node == t:
return (cost, path)
for w, n in g.get(node, ()):
oldc = dist.get(n, float("inf"))
newc = cost + w
if newc < oldc:
dist[n] = newc # relax
heappush(q, (newc, n, path))

return float("inf")```

or you can just use seen, ignore mins/dist

```from collections import defaultdict
from heapq import *

def dijkstra(edges, f, t):
g = defaultdict(list)
for l,r,c in edges:
g[l].append((c,r))

q, seen = [(0,f,())], set()
while q:
(cost,v1,path) = heappop(q)
if v1 not in seen:
path = (v1, path)
if v1 == t: return (cost, path)

for c, v2 in g.get(v1, ()):
if v2 in seen: continue
next = cost + c
heappush(q, (next, v2, path))

return float("inf")```

### lycutter commented Mar 18, 2019

Thanks for your code very much. But I want to make some expansion on this basis. The situation is that our map is a matrix, and there are more than one shortest path to reach the destination, if I want to find all the road not just the one, how to modify the code to achieve this？ Thanks again.

### nolfonzo commented Jun 18, 2019

This is a slightly simpler approach, following 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'])
"""
``````

### daidai21 commented Nov 22, 2019

Flatten path version:

```from collections import defaultdict
from heapq import *

def dijkstra(edges, f, t):
g = defaultdict(list)
for l, r, c in edges:
g[l].append((c, r))

q, seen, mins = [(0, f, [])], set(), {f: 0}
while q:
(cost, v1, path) = heappop(q)
if v1 not in seen:
path = [v1] + path
if v1 == t:
return (cost, path)

for c, v2 in g.get(v1, ()):
if v2 in seen:
continue
prev = mins.get(v2, None)
next = cost + c
if prev is None or next < prev:
mins[v2] = next
heappush(q, (next, v2, path))

return (float("inf"), [])

if __name__ == "__main__":
edges = [
("A", "B", 7),
("A", "D", 5),
("B", "C", 8),
("B", "D", 9),
("B", "E", 7),
("C", "E", 5),
("D", "E", 15),
("D", "F", 6),
("E", "F", 8),
("E", "G", 9),
("F", "G", 11)
]

print("=== Dijkstra ===")
print(edges)
print("A -> E: ", end="")
print(dijkstra(edges, "A", "E"))
print("F -> G: ", end="")
print(dijkstra(edges, "F", "G"))```
```=== Dijkstra ===
[('A', 'B', 7), ('A', 'D', 5), ('B', 'C', 8), ('B', 'D', 9), ('B', 'E', 7), ('C', 'E', 5), ('D', 'E', 15), ('D', 'F', 6), ('E', 'F', 8), ('E', 'G', 9), ('F', 'G', 11)]
A -> E: (14, ['E', 'B', 'A'])
F -> G: (11, ['G', 'F'])```

### ehborisov commented Feb 28, 2020 • edited

Hi, I think I made a bit cleaner (subjectively :)) implementation in Python that uses RBTree as a priority queue with tests there

https://github.com/ehborisov/algorithms/blob/master/8.Graphs/dijkstra.py

### coldmanck commented Mar 6, 2020 • edited

Unless I am missing something here, this is a BFS with a min-heap, not a Dijkstra's algorithm.

@JixinSiND Dijkstra's algorithm is essentially a weighted version of BFS.

### alelom commented Jun 6, 2020 • edited

Just leaving a comment to let the author know that his code has been inappropriately taken and re-used as material for teaching at a University master in London. The authorship has been modified to report the lecturer's one instead.
https://www.dcs.bbk.ac.uk/~ale/pwd/2019-20/pwd-8/src/pwd-ex-dijkstra+heap.py

### kachayev commented Jun 8, 2020

@alelom Thanks a lot for letting me know, such a kind of you! This is not the first time this code was copy-pasted into lecture materials and/or projects codebases. Honestly, if it helped students to learn - I would be glad and proud. I care less about authorship or any sort of attribution. On the one hand, I wouldn't want to encourage disrespectful actions, on the other hand, I don't have reliable way to prevent this from happening. So, choosing between spread of knowledge or nurturing morality, I would always vote for the former. Thanks again for letting me know!

### alelom commented Jun 9, 2020

I just care for what is right. If I were the lecturer, I'd quote the real author and the source – an action that does not diminish the teaching potential, and encourages sharing of good code lawfully.

### Andy9822 commented Sep 10, 2020

Thank you so much for this gift, very clean and clever solution 😄

If anyone just wonders how to easily receive as output only the value of the solution remove the cost from the return at line 15:

`if v1 == t: return cost`
`if v1 == t: return (cost, path)`

Nice and clean

### PoTseCheng commented Nov 27, 2020

Thank you very much for this beautiful algorithm.

### xdavidliu commented Dec 16, 2021

pretty sure this is not Dijkstra; you're doing `heappush(q, (next, v2, path))` at the very end, but in True dijkstra it would need a call to "decrease_key", which in python is heap._siftdown

### chausen commented Feb 27, 2022

@xdavidliu I was confused by this until I saw https://stackoverflow.com/a/31123108. I think Dijkstra's algorithm is a higher level concept, so either implementation is valid.

### tonyflow commented Mar 29, 2024

More concise with path reconstruction. The node IDs are represented as integers while the edge weights as floats

```from typing import *
from heapq import *

class Dijkstra:
def __init__(self,
graph: Dict[int, Dict[int, float]],
origin: int):
self.graph = graph
self.edge_to: Dict[int, int] = {}
self.distances: Dict[int, float] = {vertex: float('inf') for vertex in self.graph}
self.origin = origin
self._find(self.origin)

def _find(self, node: int):

self.distances[node] = 0

# Priority queue which stores tuples from distance to node id
# Distance is the first in the tuple order since it needs to have
# priority when entries are inserted into the priority queue
priority_queue: List[(float, int)] = [(node, 0)]

while priority_queue:
current_node, current_distance = heappop(priority_queue)

# If the distance currently recorded at the distances dict is
# bigger than the one pushed to the pq then we do not need to
# process this entry
if current_distance > self.distances[current_node]:
continue

for n, weight in self.graph[current_node].items():
updated_distance = current_distance + weight

if updated_distance < self.distances[n]:
self.distances[n] = updated_distance
self.edge_to[n] = current_node
heappush(priority_queue, (n, updated_distance))

def reconstruct_path(self, destination: int) -> List[int]:
node: int = destination
path: List[int] = []

while node != self.origin:
path.append(node)
node = self.edge_to[node]

path.reverse()
return path

if __name__ == '__main__':
graph = {
1: {2: 1, 3: 4},
2: {1: 1, 3: 2, 4: 5},
3: {1: 4, 2: 2, 4: 1},
4: {2: 5, 3: 1}
}

dijkstra: Dijkstra = Dijkstra(graph, 1)

print(dijkstra.distances)
print(dijkstra.reconstruct_path(4))
print(dijkstra.reconstruct_path(2))
print(dijkstra.reconstruct_path(3))```

### VeNoMouS commented Apr 1, 2024 • edited

friends don't let friends `import *` 😄

to quote pep8

Wildcard imports (from module import *) should be avoided, as they make it unclear which names are present in the namespace, confusing both readers and many automated tools. There is one defensible use case for a wildcard import, which is to republish an internal interface as part of a public API (for example, overwriting a pure Python implementation of an interface with the definitions from an optional accelerator module and exactly which definitions will be overwritten isn’t known in advance).

When republishing names this way, the guidelines below regarding public and internal interfaces still apply.