Let us consider a problem that is similar to SPSP - finding distance from to , and if possible with the same runtime - finding distance for all pairs, namely APSP.
In the proof of correctness for Dijkstra’s algorithm, we proved that after a vertex is removed from the priority queue, .
First, when solving the SSSP we can simply stop the moment vertex is removed from the queue.
We can try to improve further and imagine an expanding circle of radius that encloses all visited vertices, which in turn means .
Using this we can arrive to the following improvement, namely called the algorithm.
We’d like to not simply expand the circle in all directions but try to direct it in a way that makes us closer to the destination vertex .
To try to achieve this, let us make the key of every vertex in the priority queue a sum: where is a function called potential. We’d like to choose a function that assigns higher potential to the vertices far away from . Note that this change is rather intuitive, but actually nullifies the proof of correctness of this modification of Dijkstra.
Instead, one should modify the weights of edges of the graph, ensuring that for any path:
Clearly, a shortest path by the adjusted weights is also the shortest path by the initial weights.
It is important to note that not every function is feasible as a potential, that is, produces adjusted weights that allow for Dijkstra’s execution.
Correctness of this algorithm follows from correctness of Dijkstra and the runtime is, in the worst case, the same.
But, with a proper potential function one can terminate the algorithm much faster by only searching through “potentially good” vertices.
An excellent example of this is route searching in navigation apps. There exists a map of roads and intersections, which defines the edges and vertices of the graph, and each road has some weight, for example the average time it takes to traverse it. A potential then can be all kinds of functions, a simple choice is to take the Euclidian distance from the intersection to the destination and factor it into the weights, making the navigator prefer roads that lead to the destination directionally and only choose others if the weight of direct ones is too high.