3
$\begingroup$

Given a directed and strongly connected graph $G=(V,E)$, weight function $w: E \to \mathbb{R}$ and two distinct vertices $u,v \in V$. We know that there aren't negative cycles. I need to find algorithm, efficient as possible,such that for every value of $k$, $2 \leq k \leq |V|-1$, it will find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one).

I don't know what to do. I want to use Bellman Ford somehow, I just don't sure how.

Thanks a lot.

$\endgroup$
  • 3
    $\begingroup$ It seems that we are spending a lot of effort doing your homework for you. What have you tried? How are you approaching the problem? $\endgroup$ – Dave Clarke Aug 28 '12 at 17:14
  • $\begingroup$ This is not my home work. these are questions from past exams I'm trying to solve in order to practice myself to my exam. I don't have direction for solving the problem, as I wrote. $\endgroup$ – Jozef Aug 28 '12 at 17:35
4
$\begingroup$

Consider the dynamic programming formulation of Bellman-Ford:

$\qquad \displaystyle \mathrm{bf}(i,j) = \begin{cases} 0 &, i = 0 \land j = s \\ \infty &, i = 0 \land j \neq s \\ \min\limits_{k \in V}\, \big(\, \mathrm{bf}(i-1,k) + c(k,j)\,\big) &, \text{else} \end{cases}$

What meaning does $\mathrm{bf}(i,j)$ have, that is what does DP-matrix entry $\mathrm{bf}[i,j]$ contain?

If you unfold the definition (i.e. proof by induction) you see that $\mathrm{bf}(i,j)$ is the weight of the shortest path from starting node $s$ to $j$ with at most $i$ edges -- exactly what you are looking for.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.