Algoritmo de bellman.docx

Algoritmo de Bellman-Ford
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda
El algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas nosean negativos. 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.
Según Robert Sedgewick, “Los pesos negativos no son simplemente una curiosidad matemática; […] surgen de una forma natural en la reducción a problemas de caminos más cortos”, y son un ejemplo de unareducción del problema del camino hamiltoniano que es NP-completo hasta el problema de caminos más cortos con pesos generales. Si un grafo contiene un ciclo de coste total negativo entonces este grafo no tiene solución. El algoritmo es capaz de detectar este caso.
Si el grafo contiene un ciclo de coste negativo, el algoritmo lo detectará, pero no encontrará el camino más corto que no repite ningúnvértice. La complejidad de este problema es al menos la del problema del camino más largo de complejidad NP-Completo.

Algoritmo
El Algoritmo de Bellman-Ford es, en su estructura básica, muy parecido al algoritmo de Dijkstra, pero en vez de seleccionar vorazmente el nodo de peso mínimo aun sin procesar para relajarlo, simplemente relaja todas las aristas, y lo hace |V|-1 veces, siendo |V| elnúmero de vértices en el grafo. 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. A diferencia de la solución voraz, la cual depende de la suposición de que los pesos sean positivos, esta solución se aproxima más al caso general.
Existen dos versiones:
* Versión no optimizada paragrafos con ciclos negativos, cuyo coste de tiempo es O(VE)
* Versión optimizada para grafos con aristas de peso negativo, pero en el grafo no existen ciclos de coste negativo, cuyo coste de tiempo, es también O(VE).
BellmanFord(Grafo G, nodo_origen s)
// inicializamos el grafo. Ponemos distancias a INFINITO menos el nodo origen que
// tiene distancia 0
for v ∈ V[G]do
distancia[v]=INFINITO
predecesor[v]=NIL
distancia[s]=0
// relajamos cada arista del grafo tantas veces como número de nodos -1 haya en el grafo
for i=1 to |V[G]-1| do
for (u, v) ∈ E[G] do
if distancia[v]>distancia[u] + peso(u, v) then
distancia[v] = distancia[u] + peso (u, v)predecesor[v] = u
// comprobamos si hay ciclos negativo
for (u, v) ∈ E[G] do
if distancia[v] > distancia[u] + peso(u, v) then
print ("Hay ciclo negativo")
return FALSE
return TRUE
BellmanFord_Optimizado(Grafo G, nodo_origen s)
// inicializamos el grafo. Ponemos distancias a INFINITO menos el nodo origen que// tiene distancia 0. Para ello lo hacemos recorriéndonos todos los vértices del grafo
for v ∈ V[G] do
distancia[v]=INFINITO
padre[v]=NIL
distancia[s]=0
encolar(s, Q)
en_cola[s]=TRUE
mientras Q!=0 then
u = extraer(Q)
en_cola[u]=FALSE
// relajamos las aristas
for v ∈ ady[u] doif distancia[v]>distancia[u] + peso(u, v) then
distancia[v] = distancia[u] + peso (u, v)
padre[v] = u
if en_cola[v]==FALSE then
encolar(v, Q)
en_cola[v]=TRUE
[editar] Aplicaciones de encaminamiento
Una variante distribuida del Algoritmo del Bellman-Ford se usa en protocolos de...