Algoritmo de Floyd-Warshall

En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica.

 

Este algoritmo se puede aplicar en videojuegos para encontrar el camino más corto entre dos puntos de forma pre calculada. Es una buena forma de concentrar el uso de recursos al inicio e incluso almacenar el cálculo en tiempo de edición y cargar la información en tiempo de ejecución.

 

Tenemos una serie de puntos distribuidos en un estancia y queremos desarrollar un sistema con el que conocer el camino más corto dado un punto de partida y otro de destino.

 

Lo primero que tenemos que determinar es que puntos tienen visibilidad entre si, esto es, que no haya ningún obstáculo entre ellos.

 

Al hacerlo obtenemos también, en caso de existir visibilidad, la distancia entre los puntos.

 

Ahora creamos dos matrices de tantas filas por columnas como puntos hayan.

Una para las distancias:

En el caso en el que no exista visibilidad entre dos puntos marcaremos la distancia con infinito. En la tabla representado por &.

Otra para las direcciones:

Esta tabla la rellenamos arrastrando el indice de columna hacia abajo dejando en blanco la diagonal principal de la matriz.

Ahora empezamos a procesar ambas matrices para obtener la información que buscamos.

Filas contra Columnas:

Vamos a cruzar filas contra columnas. Cada paso en el proceso que hagamos corresponde a uno de los puntos iniciales.

Sumamos cada valor de la primera columna con todos los de la primera fila y dejamos caer el valor en la casilla correspondiente (excepto para la diagonal principal).

Cada cambio que hagamos en la matriz de distancias lo actualizaremos en la matriz de direcciones modificando la celda correspondiente con el número del punto que estamos cruzando.

Repetimos este proceso con todos los puntos.

Finalmente obtendremos una matriz de distancias que nos indicará la distancia total entre dos puntos y otra de direcciones que nos indicará a que punto debemos dirigirnos antes de llegar al destino.

Volvamos al punto inicial e imaginemos que queremos ir del punto 1 al 5.

  1. Nos fijamos en la celda [1, 5] y nos remite al punto 4.
  2. Nos fijamos en la celda [1, 4] y nos remite al punto 2.
  3. Nos fijamos en la celda [1, 2] y nos remite al punto 2. Este es el siguiente punto al que debemos destinarnos.

La distancia que recorreremos al final será de 8.2 metros.

 

Relacionado


  • Algoritmo de Dijkstra
  • Algoritmo A*

 

Enlaces externos


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *