[Math] Shortest path between three nodes in a graph

algorithmsgraph theorynumber theory

I know Dijkstra's algorithm to find the shortest way between 2 nodes, but is there a way to find the shortest path between 3 nodes among $n$ nodes? Here are the details:

I have $n$ nodes, some of which are connected directly and some of which are connected indirectly, and I need to find the shortest path between 3 of them.

For example, given $n = 6$ nodes labelled A through F, and the following graph:

A-->B-->C
A-->D-->E
D-->F

How can I find the shortest path between the three nodes (A,E,F)?

I am looking for a solution similar to Dijkstra's shortest path algorithm, but for 3 nodes instead of 2.

Please Note :
1- The Starting Node is A
2- The Sequential is not important just the path needs to cover all these Nodes
3- Their is no return back to A
Please find the diagram Image
enter image description here
Regards & Thanks
Nahed

Best Answer

For the case of a start node S and two target nodes X and Y, one could use the following algorithm:

Use Dijkstra's shortest-path algorithm to find the shortest path from S to X and the shortest path from S to Y. If path from S to X is shorter, use Dijkstra's shortest-path algorithm to find the shortest path from X to Y, and follow the paths found from S to X and then from X to Y. Else (if the second path is shorter), find the shortest path from Y to X and follow the paths found from S to Y and then from Y to X.

Since this always uses Dijkstra's algorithm exactly 3 times, it is asymptotically just as efficient as Dijkstra's algorithm.

Note that, as Tyler Olsen and ml0105 point out, if there are in fact a variable number of nodes you need to pass through instead of only 3, this problem is NP-Hard.

Related Question