← Volver a los ejercicios

Reconstruir el camino con nex

nex[i][j] es el vértice que sigue después de i en un camino más corto hacia j. El camino se arma hacia adelante: desde i se salta a nex[i][j] y se repite hasta llegar. Una de las parejas de abajo no tiene camino, y ahí los saltos llevan a una arista que no existe.

Resueltas: 0 de 6

1. El grafo

En verde el origen de la pareja en curso, en ámbar el destino y en morado los saltos que se llevan dados.

2. Las dos matrices

A la izquierda las distancias, con la pareja en curso marcada. A la derecha nex, con la columna del destino sombreada: es la que se lee salto tras salto.

3. Escriba los caminos

Los vértices separados por espacios, incluidos los dos extremos. Si la pareja no tiene camino, escriba ninguno.

4. Siga los saltos

Camino

5. Para llevarse

Sin solución aquí. Escriba la función que recibe d, nex, i y j y devuelve la lista de vértices del camino, o la lista vacía cuando no hay, con un solo return al final. Después diga qué pasa si se le quita la comparación con la distancia y se corre sobre la pareja que aquí no tiene camino.