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.
Fila que se llena ahora: . Escoja el valor de cada casilla.
Aquí aparece la explicación de cada fila que se comprueba.
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.