# Shortest path between three nodes in a graph

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.
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 Regards & Thanks
Nahed

• Can you use Floyd Warshall algorithm? Apr 28, 2014 at 21:10
• 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 Apr 28, 2014 at 21:12
• What exactly constitutes a path "between" three nodes? Apr 28, 2014 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
– JPNN
Apr 29, 2014 at 13:03
• @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. Apr 29, 2014 at 13:38

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.

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.

• 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. Apr 30, 2014 at 0:08
• I know, but the optimal Hamiltonian Path problem is a subset of the problem defined. This implies NP-Hardness immediately. Apr 30, 2014 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. Apr 30, 2014 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. Apr 30, 2014 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. Apr 30, 2014 at 0:31