Bellman-Ford: Shortest path with $k$-edges

algorithmsgraph theoryproof-writing

Let $G=(V,E)$ be a directed graph with weights $c:E\rightarrow\mathbb{R}$, $s,t\in V$ two nodes ($s\neq t$) and $k\geq 1$.

How can I use the Bellman-Ford Algorithm to determine the shortest path between $s$ and $t$ with $k$-edges (or show that there is none).

So was thinking about induction, but there was this hint that instructed to use an "extended" version of $G$ where there are multiple copies of every edge $v\in V$. This however confused my quite a bit. How could I go on, using this hint ?

Best Answer

Here is an outline.

  1. Consider $k$ copies of the vertices. Call then $V_1, \cdots, V_k$.
  2. If $(u,v)$ is an edge, connect $(u_i, v_{i+1})$ for all $i$.
  3. Run BF on $s \in V_1$ and $t \in V_k$.
Related Question