Luke Harold Miles qpwo
qpwo
/ dijkstra.py
Last active
September 22, 2022 21:01
— forked from potpath/dijkstra.py
Dijkstra's Algorithm in python using PriorityQueue. Quits early upon goal discovery. More like uniform cost search actually. Fast.
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 queue import PriorityQueue # essentially a binary heap | |
| def dijkstra(G, start, goal): | |
| """ Uniform-cost search / dijkstra """ | |
| visited = set() | |
| cost = {start: 0} | |
| parent = {start: None} | |
| todo = PriorityQueue() | |
| todo.put((0, start)) |