The title may be a bit misleading, but this is essentially a DP problem. The problem is that we have $n$ cities labeled from $1, ... n$ and we are trying to find the cheapest way to travel from 1 to $n$. There is a cost for travelling from $i$ to $j$, $i < j$, cost being $c_{ij}$ but I'm only allowed $k$ hops at most.

The $k$ constraint has me stumped. Intuitively, we recurse from $i$ to $n$ for each value of $n$. How would I solve this using at most $k$ hops? And what would the complexity be?

  • 2
    $\begingroup$ I suggest you keep thinking. Try to solve special cases like $k=1,2,3$ first. $\endgroup$ – Yuval Filmus Apr 27 '16 at 18:04
  • $\begingroup$ There's an algorithm for this. It's called Floyd-Warshall Algorithm. You may look for that if that helps. $\endgroup$ – Syed Ali Hamza Apr 27 '16 at 19:03

Your Answer

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

Browse other questions tagged or ask your own question.