I've been digging into Dijkstra's algorithm for a few days now and I get how it functions. It seems really efficient, but I still find some aspects confusing and feel like there's a bit of magic involved. Specifically, I'm trying to wrap my head around why we always select the node with the lowest distance from the starting point on the frontier. For instance, imagine we're at Node X, and the frontier has Nodes Y and Z. If Z has an infinite distance from the source, while Y has a distance of 'n' from the source (which it got from a previous path), it seems logical to choose Y. But what if Z ends up being part of a shorter path than Y's? I mean, isn't it possible that we could discover a faster way through Z? I sort of grasp that going with Y first seems more efficient since Z could potentially be longer, but I'd like to understand intuitively why Z isn't worth exploring first.
2 Answers
Well, you can definitely explore other nodes if you think they might offer a faster route—that's what A* does. However, if Z has an infinite distance, it doesn’t make sense to choose it because you can’t be sure there’s any path leading to it. Plus, the current node doesn't impact which node to choose next.
You’re right to question that! The main reason for prioritizing Y over Z is that exploring Z while it’s still at an infinite distance is essentially wasting time. If it had the potential to lower the total distance, it would already have a tentative distance less than n and would be the one chosen. So, by finalizing Y, you’re ensuring you’re on the optimal path without needing to revisit it later.
That's a good point! Dijkstra's isolates between knowing a node can be reached with a certain distance and knowing that’s the best possible distance. It works until the goal is found with the optimal path. A* just adds a twist by estimating the distance to the goal, which you wouldn’t be doing with Dijkstra’s.