1
$\begingroup$

I'm doing an online course in which I'm struggling with the following (multiple-choice) question:

Suppose we run the FLoyd-Warshall algorithm on a directed graph $G =(V,E)$ in which every edge's length is either $-1,0,$ or $1$. Suppose further that $G$ is strongly connected, with at least one $u$-$v$ path for every pair $u,v$ of vertices. The graph $G$ may or may not have a negative-cost cycle. How large can the final entries $A[i,j,n]$ be, in absolute value? Choose the smallest number that is guaranteed to be a valid upper bound. (As usual, $n$ denotes $|V|$.) [WARNING: for this question, make sure you refer to the implementation of the Floyd-Warshall algorithm given in lecture, rather than to some alternative source.]

  1. $+\infty$

  2. $n^2$

  3. $2^n$

  4. $n-1$

I'm furthermore told that $n-1$ shouldn't be selected, with the hint "Experiment with graphs that have negative-cost cycles".

Here is the Floyd-Warshall algorithm as described in the lectures:

Let $A$ be a 3-D array, indexed by $i,j,k$. Define the base cases: $$ A[i,j,0] = \begin{cases}0 & i = j \\ c_{i,j} & (i,j)\in E \\ +\infty & \text{else}\end{cases}$$

For k = 1 to n
    For i = 1 to n
        For j = 1 to n
            A[i,j,k] = min(A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1])

Correctness: From optimal substructure and induction, as usual.

Running time: $O(1)$ per sub-problem, $O(n^3)$ total.

In the course's nomenclature, $n$ denotes the total number of vertices in the graph, so $A(i, j, n)$ is the shortest path from node $i$ to $j$ which may use all $n$ nodes.

As I understand it, a shortest path between any two nodes has at most $n - 1$ edges, so if the maximum cost of an edge is 1, I would expect the maximum cost of a shortest path to be $n - 1$. I don't see how the presence of negative-cost cycles could change this?

$\endgroup$
  • 4
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Sep 18 '17 at 10:35
  • 3
    $\begingroup$ They give you a good hint: try some inputs. $\endgroup$ – Raphael Sep 18 '17 at 10:36
  • $\begingroup$ In particular, try it with a graph containing a negative-weight cycle. I'm voting to leave this open, since you do explain your reasoning and it's not just a problem dump. $\endgroup$ – David Richerby Sep 18 '17 at 10:49
  • $\begingroup$ This question has been answered here. The gist is that, for every iteration of the outer loop (i.e., for every increment of subproblem size) the shortest paths can be reduced by a factor of 2, thereby having exponential behavior. This is assuming a fully connected graph with all weights equal to -1. $\endgroup$ – Mario Cervera Sep 18 '17 at 17:57
  • 1
    $\begingroup$ +1 to @Raphael's comment. Every question ever posted by the OP are screenshots; clearly, some people are just plain lazy. I've edited two of them for better searchability. $\endgroup$ – Abhijit Sarkar Jan 7 at 2:22
2
$\begingroup$

a shortest path between any two nodes has at most n - 1 edges

This is only true for simple paths (paths with no repeat nodes). If there is a negative-cost cycle, you can take the cycle multiple times to get a shorter path.

$\endgroup$
  • 3
    $\begingroup$ Continueing that thought, there no longer is a shortest path. $\endgroup$ – Raphael Sep 18 '17 at 10:37
  • $\begingroup$ I suppose that in the presence of negative cycles, A[i, j, n] no longer represents the shortest path length. The question essentially is what it does represent, and in particular what its maximum value could be. In that regard I don't see how the presence of negative cycles could increase its value beyond that of n - 1 that it would be if the graph had no negative cycles. Perhaps you can answer this more nuanced question? $\endgroup$ – Kurt Peek Sep 18 '17 at 13:53

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.