Shortest path between two nodes multiple times

Question

In an undirected but weighted graph, I am trying to find the shortest path (distance) between two nodes multiple times. If I use Dijkstra, then I can find the distance between one node and every other node. Doing separate Dijkstras for each starting node is inefficient with O(E V logV). Is there a way for a more efficient method to do this?

What if there were some constraints, say there are n predefined nodes that I need to query the distance to any of them? Would that change the algorithm to solve this problem? I suspect there is a common algorithm for this, but I've never heard of this before. In my graph, the number of edges is approximately three times the number of nodes. (Three edges per node).

Answer 1

Yes, there is a more efficient way to find the shortest path (distance) between two nodes in an undirected weighted graph than running Dijkstra's algorithm for each starting node. One approach is to use the Bidirectional Dijkstra algorithm.

The Bidirectional Dijkstra algorithm works by running two instances of Dijkstra's algorithm at the same time, one starting from the source node and the other starting from the target node. The algorithm continues to run until the two searches meet at some node in the middle. At this point, the algorithm has found the shortest path between the two nodes.

The Bidirectional Dijkstra algorithm can be more efficient than running Dijkstra's algorithm separately for each starting node, as it explores the graph from both ends simultaneously and can stop early once the two searches meet in the middle. The time complexity of the Bidirectional Dijkstra algorithm is O(E + V log V), which is faster than the O(E V log V) time complexity of running Dijkstra's algorithm separately for each starting node.

If there are n predefined nodes that you need to query the distance to any of them, one approach is to run n instances of the Bidirectional Dijkstra algorithm, one for each predefined node as the starting node, and store the resulting distances in a data structure such as an array or a map. This way, you can look up the distances between any two nodes in constant time by querying the data structure. The time complexity of this approach is O(n(E + V log V)), which is faster than running Dijkstra's algorithm separately for each starting node, but slower than running a single instance of the Bidirectional Dijkstra algorithm.