Skip to main content
2 of 2
Added a reduction to an ordinary shortest path problem
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

If $v_1$ and $v_l$ are fixed then constructing a minimum weight breadth-first tree of height $l{-}1$ and finally optimally attach vertex $v_l$.

Iterating over all candidate pairs of $v_1$ and $v_l$ would then yield the optimal solution.

Minimum weight breadth first trees seem to be the method of choice for controlling the number of edges of paths.

Addendum:

having learned that the paths need not be simple, we can reduce the fixed-cardinality shortest path to an ordinary shortest path problem as follows:

if we require a shortest path with exactly $l{-}1$ edges and the additional constraint that the start-vertex must be from a subset $S$ and the terminal vertex from a subset $T$ of $V$, we can achieve this as follows:

  • add a super-startvertex $\mathrm{A}$ and a super-terminalvertex vertex $\Omega$, that's analogous to RobPratts idea for solving the problem via cost-flows (but we are reducing the problem to an ordinary shortest path problem).

  • generate $n$ sets $V_1=S,V_2=V,\,\dots,\,V_{l{-}1}=V,V_l=T$ of vertices, each dedicated for path whose number of edges equal the index of the vertex set.

  • put the vertices of $S=V_1$ in the adjacency list of $\mathrm{A}$ and put $\Omega$ in the adjacency lists of vertices in $V_l=T$

  • replace the adjacency lists of vertices from $V_i$ with the corresponding vertices (i.e. with the same label) from $V_{i+1}$

  • calculate in the so generated graph the shortes path from $\mathrm{A}$ to $\Omega$

In case $S$ and $T$ are not disjoint, that would also be able generate a closed cycle as an answer; if that is not desired, it must be ruled out otherwise.

Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76