Dijkstra's algorithm vs A*

The A* algorithm terminates when the f (distance + heuristic) is less than the f values for all of the nodes that haven't been visited. Dijkstra's algorithm produces the shortest path to every node from a starting point (not just the end node - the goal).

Is it possible to modify Dijkstra's algorithm so that when the distance to the end node is shorter than the distances to all of the unvisited nodes in the priority queue, we terminate the algorithm?

Yes, that is a common variant. In fact, Dijkstra himself included this early termination in his algorithm (see problem 2). So in that sense it's not really a modification, it's how Dijkstra himself described the algorithm to begin with. As Wikipedia puts it:

Dijkstra's original algorithm found the shortest path between two given nodes,[6] but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

([6] is the same paper I linked to)

However, in my perception, the original version is the more popular one.

To make the exit condition a bit more precise, the algorithm can terminate when a goal node is taken out of the frontier. That can also happen if a goal node is tied for the lowest cost with other nodes. The same applies to A*. I intentionally use "a goal", because Dijkstra's algorithm also works with multiple goals or with a predicate that is evaluated to determine whether a node is a goal node.

By the way a recurring incorrect variant of Dijkstra's algorithm is to test whether a node is the goal when it is first reached and then terminate, but this fails to take into account that as long as a node is still in the frontier, it may be possible to find a shortcut to it.

StackExchange Computer Science Q#139760, answer score: 6