Algoritmo de Bellman-Ford

En previsión del comienzo del curso "Algoritmos para desarrolladores", prepararon otra traducción de un artículo interesante.

---

Problema : Dada una gráfica y un vértice inicial src en una gráfica, es necesario encontrar las rutas más cortas desde src a todos los vértices en una gráfica dada. El gráfico puede contener aristas con pesos negativos.

Ya hemos discutido el algoritmo de Dijkstra como una forma de resolver este problema. El algoritmo de Dijkstra es un algoritmo codicioso, y su complejidad es O (VLogV) (usando el montón de Fibonacci). Sin embargo, Dijkstra no funciona para gráficos con pesos de borde negativos, mientras que Bellman-Ford lo es por completo. El algoritmo de Bellman-Ford es aún más simple que el algoritmo de Dijkstra y es muy adecuado para sistemas distribuidos. Al mismo tiempo, su complejidad es O (VE) , que es más que el indicador del algoritmo de Dijkstra.

Recomendación : antes de pasar a ver la solución, intente practicar usted mismo.

Algoritmo

Los siguientes son pasos detallados.

Entrada : Gráfico y vértice inicial src .
Salida : La distancia más corta a todos los vértices desde src. Si se produce un ciclo de peso negativo, no se calculan las distancias más cortas, se muestra un mensaje que indica la presencia de dicho ciclo.

1. En este paso, las distancias desde el vértice inicial a todos los demás vértices se inicializan como infinitas, y se supone que la distancia a src es 0. Una matriz dist[] tamaño |V| con todos los valores iguales al infinito, con la excepción del elemento dist[src] , donde src es el vértice original.
2. El segundo paso calcula las distancias más cortas. Se deben realizar los siguientes pasos |V| -1 veces, donde |V| - el número de vértices en este gráfico.
   
   • Realice la siguiente acción para cada borde uv :
     Si dist[v] > dist[u] + uv , entonces actualice dist[v]
dist [v] = dist [u] + uv
     
3. En este paso, se informa si hay un ciclo de peso negativo en el gráfico. Para cada borde uv , haga lo siguiente:
   
   
   • Si dist[v] > dist[u] + uv , entonces el gráfico contiene un ciclo de peso negativo.
     

La idea del paso 3 es que el paso 2 garantiza la distancia más corta si el gráfico no contiene un ciclo de peso negativo. Si volvemos a recorrer todos los bordes y obtenemos un camino más corto para cualquiera de los vértices, esto será una señal de la presencia de un ciclo de peso negativo.

Como funciona Como en otras tareas de programación dinámica, el algoritmo calcula las rutas más cortas de abajo hacia arriba. Primero, calcula las distancias más cortas, es decir, caminos con una longitud de no más de un borde. Luego calcula las rutas más cortas con una longitud de no más de dos aristas, y así sucesivamente. Después de la iteración i-ésima del bucle externo, se calculan las rutas más cortas con una longitud de no más de i aristas. En cualquier ruta simple, puede haber un máximo de | V | -1 aristas, por lo que el bucle externo se ejecuta exactamente | V | -1 veces. La idea es que si calculamos la ruta más corta con no más de i bordes, iterar sobre todos los bordes garantiza obtener la ruta más corta con no más de i + 1 bordes (la prueba es bastante simple, puede consultar esta conferencia o video del MIT )

Ejemplo

Veamos el algoritmo en el siguiente ejemplo de gráfico. Imágenes tomadas desde aquí .
Deje que el vértice inicial sea 0. Tome todas las distancias como infinitas, excepto la distancia para src . El número total de vértices en el gráfico es 5, por lo que todos los bordes deben ir 4 veces.



Deje que las costillas se trabajen en el siguiente orden: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), ( E, D). Obtenemos las siguientes distancias cuando el pasaje a lo largo de las costillas se completó por primera vez. La primera línea muestra las distancias iniciales, la segunda línea muestra las distancias cuando se procesan los bordes (B, E), (D, B), (B, D) y (A, B). La tercera línea muestra la distancia de procesamiento (A, C). La cuarta línea muestra lo que sucede cuando se procesan (D, C), (B, C) y (E, D).



La primera iteración asegura que todas las rutas más cortas no sean más largas que la ruta de 1 arista. Obtenemos las siguientes distancias cuando se completa la segunda pasada en todos los bordes (la última línea muestra los valores finales).



La segunda iteración asegura que todas las rutas más cortas tengan una longitud de como máximo 2 aristas. El algoritmo se ejecuta a lo largo de todos los bordes 2 veces más. Las distancias se minimizan después de la segunda iteración, por lo que la tercera y la cuarta iteraciones no actualizan los valores de distancia.

Implementación

 # Python program for Bellman-Ford's single source # shortest path algorithm. from collections import defaultdict # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # default dictionary to store graph # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("% d \t\t % d" % (i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float("Inf")] * self.V dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. A simple shortest # path from src to any other vertex can have at-most |V| - 1 # edges for i in range(self.V - 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print "Graph contains negative weight cycle" return # print all distance self.printArr(dist) g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # Print the solution g.BellmanFord(0) # This code is contributed by Neelam Yadav 

Valores de salida:



Notas:

1. Los pesos negativos se encuentran en varias aplicaciones de gráficos. Por ejemplo, en lugar de aumentar el costo de una ruta, podemos beneficiarnos siguiendo una ruta específica.
2. El algoritmo Bellman-Ford funciona mejor para sistemas distribuidos (mejor que el algoritmo de Dijkstra). A diferencia de Dijkstra, donde necesitamos encontrar el valor mínimo de todos los vértices, en Bellman Ford, los bordes se consideran uno a la vez.

Ejercicios:

1. El algoritmo estándar de Bellman-Ford informa los caminos más cortos solo si no tiene ciclos de peso negativo. Modifíquelo para que informe las rutas más cortas incluso si existe tal ciclo.
2. ¿Podemos usar el algoritmo de Dijkstra para encontrar las rutas más cortas en un gráfico con pesos negativos? Existe una idea así: calcule el valor de peso mínimo, agregue un valor positivo (igual al valor absoluto del valor de peso mínimo) a todos los pesos y ejecute el algoritmo Dijkstra para el gráfico modificado. ¿Funcionará tal algoritmo?

Implementación simple del algoritmo Bellman-Ford

Fuentes:

www.youtube.com/watch?v=Ttezuzs39nk
en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf