← Volver a los ejercicios

El triple ciclo sobre la matriz

Se ejecuta floydWarshall, la versión de una sola matriz, línea por línea. El arranque ya corrió: d es la matriz de pesos con la diagonal en 0. El número que acompaña a cada línea es el de su archivo, y el contador dice cuántas veces se ejecuta.

1. El grafo y la predicción

En ámbar, el vértice k de la pasada en curso. En azul claro, el vértice i de la fila que se está recorriendo.
¿Cuántas veces se ejecuta la línea 57, la que baja una distancia, en toda la corrida?

2. Ejecute el código

Paso 0 de 0
Pasadas

3. La matriz

Sombreadas, la fila k y la columna k, que la pasada lee y no mueve. Con borde ámbar, la pareja que se está mirando; en verde, la que acaba de bajar.

4. Lo que cuesta

5. Para llevarse

Sin solución aquí. Lleve la corrida hasta el final y mire la columna de una pareja que nunca bajó: escriba la comparación que la línea 56 hizo en cada uno de los pasos y diga por qué ninguna fue cierta. Después agregue al primer grafo una arista de peso 1 del último vértice al primero y diga cuántas veces correría la línea 57.