1
$\begingroup$

I recently learned Ford's algorithm to find the shortest paths in a digraph without any cost-negative cycles. To estimate its efficiency, we learned that it has at most $C \cdot n^2$ steps with $C := 1 + 2 \cdot \text{max}\{|c_{(a,b)}| : (a,b) \in A\}$ where $n$ is the number of vertices, $A$ are the edges and $c$ are the associated costs which are all integers.

I really struggle with understanding why the highest cost is relevant for how many iterations are needed. Can anyone explain this to me?

$\endgroup$
2
$\begingroup$

The proof of convergence of the algorithm shows that the cost decreases after each iteration, and since it can decrease by as little as one unit, it stands to reason that the number of iteration is bounded by $C$ times cost of the iteration.

$\endgroup$
2
  • $\begingroup$ But since the costs can also be negative, should this then not be the maximum difference of costs instead of the absolute maximum cost? $\endgroup$
    – Max
    May 3 at 16:37
  • $\begingroup$ the maximum difference of costs would be at most twice the maximum cost in absolute value, which is basically how you defined C $\endgroup$
    – dbal
    May 4 at 12:49

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.