← Volver a los ejercicios

A lo sumo k aristas

La fila k de la tabla guarda, para cada vértice, el costo del camino más corto desde el origen que usa a lo sumo k aristas. La fila 0 solo conoce al origen, y cada fila nueva se calcula a partir de la anterior: para cada arista (u, v) de peso w se compara lo que ya tenía v con dist[u] + w, usando el dist[u] de la fila de arriba. Se llena la tabla fila por fila de k = 0 a n − 1 en tres grafos, y la comprobación de cada fila dice qué camino mejoró y por qué hizo falta una arista más. En el último grafo hay un ciclo negativo y hay que seguir hasta la fila n.

1. El grafo

El origen va en verde y sobre cada vértice está el dist de la última fila comprobada. Las aristas verdes son las que mejoraron en esa fila; en la fila n del último grafo, las rojas forman el ciclo negativo.

2. La tabla, fila por fila

Fila que se llena ahora: . Escoja el valor de cada casilla.

3. Qué mejoró en cada fila

Aquí aparece la explicación de cada fila que se comprueba.

4. Para llevarse

Sin solución aquí. En el segundo grafo, diga en qué fila deja de cambiar la tabla y por qué no hace falta mirar la fila 6. En el tercero, explique por qué la fila 4 parece una respuesta y la fila 5 la desmiente, y qué pasaría en la fila 6.