Largest possible cost of a shortest path in which every edge's length is either -1, 0, or 1

Question

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?

Answer 1

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.