Algoritmo de Bellman-Ford

El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos, salvo que el grafo sea dirigido y sin ciclos.

Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo.

Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.

Las repeticiones permiten a las distancias mínimas recorrer el árbol, ya que en la ausencia de ciclos negativos, el camino más corto solo visita cada vértice una vez.

Se compone de los siguientes pasos: Las desventajas principales del algoritmo de Bellman-Ford en este ajuste son: En 1970 Yen describió una mejora del algoritmo Bellman-Ford para un grafo sin ciclos con peso negativo.

En esta tabla se muestran las soluciones parciales que se han ido obteniendo a través de la realización del algoritmo. Un ejemplo de la resolución final del algoritmo.