Hay algunas cosas que no entiendo sobre el algoritmo de ruta más corta de Floyd. Solicite ayuda.

La esencia del algoritmo de Floyd es la programación dinámica, que se puede escribir en tres dimensiones para comprender

f[k][i][j] significa que si el punto de partida y el final Se eliminan los puntos, la ruta solo contiene números del 1 al Para el punto k, la ruta más corta desde el punto i al punto j es f[k][i][j]

Luego expandimos k secuencialmente. se expande de 1 a n, también se obtiene la respuesta final

Considere cómo pasar de k a k+1. En primer lugar, el camino más corto no puede pasar dos veces por el punto k+1, por lo que un camino más corto que incluya el punto k+1 debe ser un camino que solo contenga los puntos 1~k P1+(punto k+1)+el otro extremo El camino P2 que contiene solo los puntos 1 ~ k se obtiene enumerando el punto i y el punto final j, y la longitud del empalme es f [k] [i] [k + 1] + f [k] [k + 1] [ j ]

Después de una observación cuidadosa, encontrará que eliminar la primera dimensión no afecta la respuesta en absoluto. Después de eliminar la primera dimensión, obtendrá el algoritmo de Floyd almacenado en una matriz bidimensional.