algoritmos de grafos

Algoritmo de Bellman-Ford

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 no sean 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.

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| el nú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
Pseudocódigo

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

http://es.wikipedia.org/wiki/Algoritmo_de_Bellman-Ford