Algoritmos "inteligentes"

Las búsquedas en profundidad y en anchura no permiten encontrar el camino más corto, aunque sí el primero que permite alcanzar el punto de destino desde el punto de partida.

Existen otros algoritmos que permiten determinar el camino más corto, o al menos un camino optimizado, sin tener que comprobar necesariamente todas las rutas posibles.

1. Algoritmo de Bellman-Ford Bellman-Ford

El algoritmo de Bellman-Ford permite encontrar el camino más corto, si existe. No es el óptimo, pero es el que funciona en la mayoría de casos. En efecto, permite definir longitudes negativas para los arcos, y no solamente positivas.

Además, si hay algún circuito cuya longitud sea negativa (y, por tanto, que permita disminuir el peso total), es capaz de detectarlo. Esto es importante, pues en este caso no existe ruta más corta.

a. Principio y pseudo-código

Este algoritmo va a utilizar la matriz de longitudes. Su funcionamiento es iterativo.

Al principio, se inicializa a +∞ la longitud mínima de cada nodo (lo que significa que no se ha encontrado todavía ningún camino hasta allí desde el destino). Se va a guardar, también, para cada nodo el nodo anterior (el que permite llegar a él de la manera óptima en longitud) e inicializarlo con un nodo vacío.

Se aplica, a continuación, tantas veces como número de nodos menos 1 mida el mismo bucle. De este modo, si tenemos 7 nodos, se aplica 6 veces.

Con cada iteración...

Si desea saber más, le proponemos el siguiente libro:
couv_DPT2INT.png
60-signet.svg
Versión impresa
20-ecran_lettre.svg
Versión online
41-logo_abonnement.svg
En ilimitado con la suscripción ENI
130-boutique.svg
En la tienda oficial de ENI
Anterior
Algoritmos exhaustivos de búsqueda de rutas
Siguiente
Dominios de aplicación