Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Can you use Floyd Warshall algorithm? –  Phicar Apr 28 at 21:10
1  
I believe what you're describing is called the "Travelling salesman problem." This is a known np-hard problem in computer science. Therefore, there is no "fast" algorithm like Dijkstra's for this one. This is explained in great detail on the wikipedia page. en.wikipedia.org/wiki/Travelling_salesman_problem –  Tyler Olsen Apr 28 at 21:12
1  
What exactly constitutes a path "between" three nodes? –  Istvan Chung Apr 28 at 21:28
    
Hi @IstvanChung , the path weight between all nodes are equals , example : from A --> B is one , also from B--> C will be 1 so from A --> C will 2 because (2 steps) . is that what you mean by the constiutions of a Path between the three nodes .Many thanks –  Nahed Apr 29 at 13:03
1  
@Nahed So in your example, the path must start at A, go through E, and end at F? Please clarify what "a path between three nodes" means. –  Istvan Chung Apr 29 at 13:38

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer
    
I believe that the problem as described is merely to find the shortest path from a start node passing through two other nodes, not the shortest path traversing all nodes. –  Istvan Chung Apr 30 at 0:08
    
I know, but the optimal Hamiltonian Path problem is a subset of the problem defined. This implies NP-Hardness immediately. –  ml0105 Apr 30 at 0:23
    
I don't understand. Could you please provide a reduction from the Hamiltonian Path problem to this problem? AFAICT the path described in this problem does not necessarily have to pass through every node in the graph. –  Istvan Chung Apr 30 at 0:25
    
The problem states: given a set of vertices and a proper subset of those vertices, find the shortest path through all the vertices in the subset. What happens if you are given all vertices in the graph? That's the optimal Hamiltonian Path problem. And so the Hamiltonian Path problem is a subset of this problem. –  ml0105 Apr 30 at 0:30
    
No, it states: given a set of vertices and a proper subset of size 3 of those vertices, find the shortest path through all the vertices in the subset. –  Istvan Chung Apr 30 at 0:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.