Floyd's Algorithm (Shortest Paths) Issue - C++

Question

Basically, I'm tasked with implementing Floyd's algorithm to find the shortest path of a matrix. A value, in my case, arg, is taken in and the matrix becomes size arg*arg. The next string of values are applied to the matrix in the order received. Lastly, a -1 represents infinity.

To be quite honest, I've no idea where my problem is coming in. When ran through the tests, the first couple pass, but the rest fail. I'll only post the first two failures along with the passes. I'll just post the relevant segment of code.

int arg, var, i, j;

cin >> arg;

int arr[arg][arg];

for (i = 0; i < arg; i++)
{
    for(j = 0; j < arg; j++)
    {
        cin >> var;
        arr[i][j] = var;
    }
}


for(int pivot = 0; pivot < arg; pivot++)
{
    for(i = 0; i < arg; i++)
    {
        for(j = 0; j < arg; j++)
        {
            if((arr[i][j] > (arr[i][pivot] + arr[pivot][j])) && ((arr[i][pivot] != -1) && arr[pivot][j] != -1))
            {
                arr[i][j] = (arr[i][pivot] + arr[pivot][j]);
                arr[j][i] = (arr[i][pivot] + arr[pivot][j]);
            }
        }
    }
}

And here are the failures that I'm receiving. The rest of them get longer and longer, up to a 20*20 matrix, so I'll spare you from that:

floyd> 
 * * * Program successfully started and correct prompt received. 

floyd 2 0 14 14 0
0 14 14 0 
floyd>   PASS  : Input "floyd 2 0 14 14 0" produced output "0 14 14 0".  

floyd 3 0 85 85 85 0 26 85 26 0
0 85 85 85 0 26 85 26 0 
floyd>   PASS  : Input "floyd 3 0 85 85 85 0 26 85 26 0" produced output "0 85 85 85 0 26 85 26 0".  

floyd 3 0 34 7 34 0 -1 7 -1 0
0 34 7 34 0 -1 7 -1 0 
floyd>   FAIL  : Input "floyd 3 0 34 7 34 0 -1 7 -1 0" did not produce output "0 34 7 34 0 41 7 41 0".  

floyd 4 0 -1 27 98 -1 0 41 74 27 41 0 41 98 74 41 0
0 -1 27 68 -1 0 41 74 27 41 0 41 68 74 41 0 
floyd>   FAIL  : Input "floyd 4 0 -1 27 98 -1 0 41 74 27 41 0 41 98 74 41 0" did not produce output "0 68 27 68 68 0 41 74 27 41 0 41 68 74 41 0".

Answer 1

Imagine the situation arr[i][j] == -1, obviously (arr[i][j] > (arr[i][pivot] + arr[pivot][j])) && ((arr[i][pivot] != -1) && arr[pivot][j] != -1) fails, but it shouldn’t if arr[i][pivot] and arr[pivot][j] are not -1

Since you are using -1 instead of infinity, you have to have something like if ((arr[i][j] == -1 || arr[i][j] > (arr[i][pivot] + arr[pivot][j])) && ((arr[i][pivot] != -1) && arr[pivot][j] != -1)) i.e. you check against 2 things: the first one is your condition and the 2nd one is the situation when arr[i][j] is infinity and the path through pivot exists, as in this case any valid path is less then infinity.