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") |
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:
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"), [])
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'])
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
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.
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
@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!
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.
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
instead of
if v1 == t: return (cost, path)
Nice and clean
Thank you very much for this beautiful algorithm.
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
@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.
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"""
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')