# Dijkstra algorithm under constraint

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 ?

• Could you clarify what output you expect? Dijkstra's algorithm does not find a path connecting all the vertices together; it finds the shortest path from one particular vertice to each other, forming a star-like tree. Also, finding a hamiltonian path is NP-hard. – Adayah Jul 23 '17 at 9:51

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.