Anexo:Ejemplo de Algoritmo de Bellman - Ford
En este artículo se mostrará un ejemplo del Algoritmo de Bellman-Ford. Para ello se mostrará la siguiente tabla y a partir de esta se explicará el procedimiento para hallar el camino mínimo de todos los vértices a un único vértice destino.
Ejemplo[editar]
Grafo inicial y Tabla de relaciones[editar]
En este ejemplo partimos de este grafo, cuyas relaciones están expuestas a su derecha:
Tabla de resolución final[editar]
En esta tabla se muestran las soluciones parciales que se han ido obteniendo a través de la realización del algoritmo.
Explicación del algoritmo[editar]
En la tabla anterior donde queda desarrollado el algoritmo paso por paso, podemos apreciar que la resolución del algoritmo viene dada por aplicar las fórmulas que vienen escritas en el paso n, a cada paso. El objetivo del algoritmo es encontrar el camino mínimo desde todos los nodos al vértice 1. En las fórmulas donde viene D, es la distancia mínima desde el nodo que aparece en el subíndice al vértice destino, en este caso, el vértice 1.
- En el paso 0, inicializamos todas las distancias mínimas a INFINITO.
- En el paso 1, actualizamos el paso anterior, aplicando las fórmulas. En este caso ponemos la distancia de los nodos que tienen accesos directos al vértice 1 y se la sumamos a la distancia mínima acumulada que hay hasta el vértice oportuno. Aquí esta distancia acumulada sería 0 para 1, debido a que sería la distancia a él mismo, e infinito para el resto porque no han sido analizados todavía.
- En el paso 2, al saber ya una distancia mínima acumulada desde los nodos 2 y 3 hasta 1, podemos actualizar las distancias mínimas de los nodos 4 y 5.
- En los pasos sucesivos, se van actualizando las distancias mínimas acumuladas (D) de los distintos vértices hasta 1, y se van utilizando en los pasos siguientes para optimizar el camino mínimo. El final del algoritmo se da cuando no hay ningún cambio de un paso a otro, es decir, cuando ya no se puede encontrar un camino más corto.