Problema del algoritmo de Floyd (rutas más cortas): C++

Question

Básicamente, tengo la tarea de implementar el algoritmo de Floyd para encontrar el camino más corto de una matriz.Se toma un valor, en mi caso, arg, y la matriz adquiere el tamaño arg*arg.La siguiente cadena de valores se aplica a la matriz en el orden recibido.Por último, un -1 representa el infinito.

Para ser honesto, no tengo idea de dónde viene mi problema.Cuando se realizan las pruebas, las primeras pasan, pero el resto falla.Sólo publicaré los dos primeros fallos junto con los pases.Simplemente publicaré el segmento de código relevante.

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]);
            }
        }
    }
}

Y aquí están los fallos que estoy recibiendo.El resto se hacen cada vez más largos, hasta una matriz de 20*20, así que te ahorraré eso:

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

imagina la situacion arr[i][j] == -1, obviamente (arr[i][j] > (arr[i][pivot] + arr[pivot][j])) && ((arr[i][pivot] != -1) && arr[pivot][j] != -1) falla, pero no debería hacerlo si arr[i][pivot] y arr[pivot][j] no son -1

Ya que estas usando -1 en lugar de infinito, tienes que tener algo como if ((arr[i][j] == -1 || arr[i][j] > (arr[i][pivot] + arr[pivot][j])) && ((arr[i][pivot] != -1) && arr[pivot][j] != -1)) es decir.verificas 2 cosas:La primera es tu condición y la segunda es la situación en la que arr[i][j] es el infinito y el camino a través pivot existe, ya que en este caso cualquier camino válido es menor que infinito.