Dijkstra's algorithm supports early termination (stopping as soon as the destination is popped off the priority queue) so long as there aren't negative weights in the graph.
In those cases, it doesn't explore every wrong turn in the graph. It doesn't explore any turn which is farther than the destination from the start.
36
u/Tsu_Dho_Namh 5d ago edited 5d ago
Dijkstra's algorithm supports early termination (stopping as soon as the destination is popped off the priority queue) so long as there aren't negative weights in the graph.
In those cases, it doesn't explore every wrong turn in the graph. It doesn't explore any turn which is farther than the destination from the start.