Shortest path in weighted digraph, constrained to include a minimum number of nodes

Question

Say you have a weighted digraph with n nodes. And you want to find the shortest path to all n nodes from a source node. But you are constrained by the fact that the shortest path must go through a minimum number of other nodes, but can only touch any given node once in a given path. Are there any algorithms which could be useful in this case?

Answer 1

There are two constraints in this problem:

1. The shortest path from the source to a node should not go through any node more than once. The only case in which going through a node more than once may reduce the cost of a path is when it contains a cycle of negative cost. However, under the constraint that the number of nodes must be minimum, there can be no negative cycles. Hence this constraint has no effect.

2. The shortest path must go through a minimum number of other nodes. Said otherwise, the shortest path must be chosen among those with minimum number of edges. This is accommodated by adopting an edge cost with two components. The first component is $1$ for every edge and the second component is the length of the edge. Given costs $c_1 = (n_1,l_1)$ and $c_2 = (n_2,l_2)$, we have $c_1 < c_2$ if and only if $n_1 < n_2$ or $n_1 = n_2$ and $l_1 < l_2$. Costs are added component-wise.

Since all edge costs are effectively positive, Dijkstra's algorithm works.