← Volver a los ejercicios

El orden de los tres ciclos

Seis variantes del mismo cuerpo, cambiando el orden en que se anidan los ciclos de k, i y j. Para cada una se decide si deja en la matriz las distancias y se escoge la razón. Al comprobar aparece la matriz que esa variante deja de verdad, corrida sobre el grafo de abajo, con las parejas que no coinciden marcadas.

Resueltas: 0 de 6

El grafo de prueba

Cinco vértices en un ciclo numerado al revés del recorrido, más la arista 4 → 0 de peso 20, en ámbar, que es cara pero existe.

Las distancias

Es contra esta matriz que se compara cada variante.

Para llevarse

Sin solución aquí. Las variantes que fallan dejan d[2][0] en 29 o varias parejas en ∞. Escriba, para una de ellas, en qué momento de la corrida se decide ese 29 y qué valor tenía d[0][2] entonces. Después construya el grafo más pequeño que distinga k, i, j de i, j, k y diga cuántos vértices y cuántas aristas necesita.