How to find the shortest route to complete the journey?

Question

Suppose we have an undirected graph:

{A,B} 5

{A,C} 6

{A,D} 3

{A,E} 4

{B,C} 4

{B,D} 3

{B,E} 6

{C,D} 3

{C,E} 5

{D,E} 5

where numbers represent the weight.

Lets say I am interested in starting from A and visiting B,C and E. How can I find the shortest route to undertake this journey? There is no destination, I just want to travel those three vertexes having traveled the shortest distance to do so. I am using the Dijkstra's algorithm with help of a heap, how can I modify the algorithm to achieve this as there is no final destination.

Answer 1

A simple approach, probably not the most efficient, but easy to implement.

1. Generate all permutations of nodes that you want to visit, in your example:

• A -> B -> C -> E
• A -> B -> E -> C
• A -> C -> B -> E
• A -> C -> E -> B
• A -> E -> B -> C
• A -> E -> C -> B

2. For each possible sequence calculate the path with Dijkstra

• E.g. for A B C E, PATH = dist(A,B) + dist(B,C) + dist(C,E)

3. Select the shortest calculated path

Other possible approaches, here, with a comparison table of relative complexity at the end:

https://www.baeldung.com/cs/shortest-path-to-nodes-graph