I have N vertices one being the source. I would like to find the shortest path that connects all the vertices together (so a N-steps path) with the constraint that all the vertices cannot be visited at whichever step.
A network is defined by N the number of vertices, the source, the cost to travel between each pair of vertices and, for each step the list of vertices that can be visited
For example, if N=5 and the vertices are 1(the source),2,3,4 and 5, the list [[2, 3, 4], [2, 3, 4, 5], [2, 3, 4, 5], [3, 4, 5]] means that for step 2 only vertices 2,3 and 4 can be visited and so forth…
I can't figure out how to adapt the Dijkstra algorithm to my problem. I would really like some ideas
Or maybe a better solution is to find something else, are there others algorithm that can handle this problem ?
Best Answer
Even the problem of finding a Hamiltonian path is NP-hard, so certainly the same holds for your problem.
Apart from that, your problem resembles the travelling salesman problem (TSP), which is also NP-hard, but a reduction from TSP to your problem is not as obvious. I shall illustrate how a solution to your problem can be used to solve TSP. We are given an undirected graph $G = (V,E)$ and a weight function $w : E \to \mathbb{R}$; our task is to transform this input so that we can find a minimum weight Hamilton cycle using an algorithm for your problem. We take one vertex $v \in V$ and duplicate it, so that its clone $v'$ has the exact same set of neighbours and weights. Now we specify that $v$ is the only vertex that may be visited in the first step, and $v'$ is the only vertex that may be visited in the last step. In all the intermediate steps, any other vertex may be visited. Using an algorithm for your problem, we find a minimum weight Hamiltonian path starting in $v$ and ending in $v'$. This corresponds to a minimum weight Hamiltonian cycle in the original graph, so we have solved the travelling salesman problem.
As far as we know, no simple modification of Dijkstra's algorithm (or any other polynomial time algorithm) is going to solve this; see P versus NP.