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") |
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.
Flatten path version: