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-->FHow 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 ImageRegards & Thanks
Nahed
2 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$I'd say Phicar's solution of Floyd-Warshall's all-pairs, shortest paths algorithm is your best choice. Of course, this problem is NP-Hard. It's the optimal Hamiltonian Path problem, which is equivalent to the Traveling Salesman Problem.
The Floyd-Warshall algorithm can be executed in polynomial time. However, while sequence of the vertices may not matter to you, it does matter in minimizing the total cost. So your reduction is really from SAT. You really have to try combinations until you get the minimum sized path.
$\endgroup$ 6
