Dado un gráfico y un vértice de origen src en el gráfico, encuentre las rutas más cortas desde src a todos los vértices en el gráfico dado. El gráfico puede contener bordes de peso negativos.
Hemos discutido el algoritmo de Dijkstra para este problema. El algoritmo de Dijkstra es un algoritmo Greedy y la complejidad del tiempo es O((V+E)LogV) (con el uso del montón de Fibonacci). Dijkstra no funciona para gráficos con pesos negativos, Bellman-Ford funciona para dichos gráficos. Bellman-Ford también es más simple que Dijkstra y se adapta bien a los sistemas distribuidos. Pero la complejidad temporal de Bellman-Ford es O(VE), que es más que Dijkstra.
Algoritmo:
Los siguientes son los pasos detallados.
Entrada: gráfico y un vértice de origen src
Salida: distancia más corta a todos los vértices desde src . Si hay un ciclo de peso negativo, entonces no se calculan las distancias más cortas, se informa el ciclo de peso negativo.
1) Este paso inicializa las distancias desde la fuente a todos los vértices como infinitas y la distancia a la fuente misma como 0. Cree una array dist[] de tamaño |V| con todos los valores infinitos excepto dist[src] donde src es el vértice de origen.
2) Este paso calcula las distancias más cortas. Haz lo siguiente |V|-1 veces donde |V| es el número de vértices en el gráfico dado.
….. a) Haga lo siguiente para cada borde uv
………………Si dist[v] > dist[u] + peso del borde uv, entonces actualice dist[v]
………………….dist[v ] = dist[u] + peso del borde uv
3) Este paso informa si hay un ciclo de peso negativo en el gráfico. Haga lo siguiente para cada borde uv
… Si dist[v] > dist[u] + peso del borde uv, entonces “El gráfico contiene un ciclo de peso negativo”
La idea del paso 3 es que el paso 2 garantiza las distancias más cortas si el gráfico no contiene un ciclo de peso negativo. Si iteramos a través de todos los bordes una vez más y obtenemos una ruta más corta para cualquier vértice, entonces hay un ciclo de peso negativo
¿Como funciona esto? Al igual que otros problemas de programación dinámica, el algoritmo calcula las rutas más cortas de forma ascendente. Primero calcula las distancias más cortas que tienen como máximo un borde en la ruta. Luego, calcula los caminos más cortos con 2 aristas como máximo, y así sucesivamente. Después de la i-ésima iteración del bucle exterior, se calculan los caminos más cortos con como máximo i aristas. Puede haber un máximo de |V| – 1 aristas en cualquier camino simple, por eso el ciclo externo ejecuta |v| – 1 vez. La idea es, asumiendo que no hay un ciclo de peso negativo, si hemos calculado las rutas más cortas con como máximo aristas i, entonces una iteración sobre todas las aristas garantiza dar la ruta más corta con aristas como máximo (i+1) (La prueba es simple , puede consultar esto o MIT Video Lecture )
Ejemplo:
Entendamos el algoritmo con el siguiente gráfico de ejemplo. Las imágenes están tomadas de esta fuente.
Sea 0 el vértice fuente dado. Inicialice todas las distancias como infinitas, excepto la distancia a la fuente misma. El número total de vértices en el gráfico es 5, por lo que todos los bordes deben procesarse 4 veces.
Deje que todos los bordes se procesen 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 todos los bordes se procesan por primera vez. La primera fila muestra las distancias iniciales. La segunda fila muestra las distancias cuando se procesan los bordes (B, E), (D, B), (B, D) y (A, B). La tercera fila muestra las distancias cuando se procesa (A, C). La cuarta fila muestra cuándo se procesan (D, C), (B, C) y (E, D).
La primera iteración garantiza dar todos los caminos más cortos que tienen como máximo 1 borde de largo. Obtenemos las siguientes distancias cuando todos los bordes se procesan por segunda vez (la última fila muestra los valores finales).
La segunda iteración garantiza dar todos los caminos más cortos que tienen como máximo 2 aristas de largo. El algoritmo procesa todos los bordes 2 veces más. Las distancias se minimizan después de la segunda iteración, por lo que las iteraciones tercera y cuarta no actualizan las distancias.
Implementación:
C++
// A C++ program for Bellman-Ford's single source
// shortest path algorithm.
#include <bits/stdc++.h>
// a structure to represent a weighted edge in graph
struct Edge {
int src, dest, weight;
};
// a structure to represent a connected, directed and
// weighted graph
struct Graph {
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges.
struct Edge* edge;
};
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
// A utility function used to print the solution
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", 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
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
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 (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX
&& dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
// 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 (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX
&& dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return; // If negative cycle is detected, simply
// return
}
}
printArr(dist, V);
return;
}
// Driver program to test above functions
int main()
{
/* Let us create the graph given in above example */
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
// add edge 0-1 (or A-B in above figure)
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
// add edge 1-4 (or B-E in above figure)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
}
Java
// A Java program for Bellman-Ford's single source shortest path
// algorithm.
import java.util.*;
import java.lang.*;
import java.io.*;
// A class to represent a connected, directed and weighted graph
class Graph {
// A class to represent a weighted edge in graph
class Edge {
int src, dest, weight;
Edge()
{
src = dest = weight = 0;
}
};
int V, E;
Edge edge[];
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
// The main function that finds shortest distances from src
// to all other vertices using Bellman-Ford algorithm. The
// function also detects negative weight cycle
void BellmanFord(Graph graph, int src)
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i = 0; i < V; ++i)
dist[i] = Integer.MAX_VALUE;
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 (int i = 1; i < V; ++i) {
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
// 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 (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
}
// A utility function used to print the solution
void printArr(int dist[], int V)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; ++i)
System.out.println(i + "\t\t" + dist[i]);
}
// Driver method to test above function
public static void main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
Graph graph = new Graph(V, E);
// add edge 0-1 (or A-B in above figure)
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
// add edge 1-4 (or B-E in above figure)
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
graph.BellmanFord(graph, 0);
}
}
// Contributed by Aakash Hasija
Python3
# Python3 program for Bellman-Ford's single source
# shortest path algorithm.
# Class to represent a graph
class Graph:
def __init__(self, vertices):
self.V = vertices # No. of vertices
self.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("{0}\t\t{1}".format(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 _ 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)
# Initially, Contributed by Neelam Yadav
# Later On, Edited by Himanshu Garg
C#
// A C# program for Bellman-Ford's single source shortest path
// algorithm.
using System;
// A class to represent a connected, directed and weighted graph
class Graph {
// A class to represent a weighted edge in graph
class Edge {
public int src, dest, weight;
public Edge()
{
src = dest = weight = 0;
}
};
int V, E;
Edge[] edge;
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
// The main function that finds shortest distances from src
// to all other vertices using Bellman-Ford algorithm. The
// function also detects negative weight cycle
void BellmanFord(Graph graph, int src)
{
int V = graph.V, E = graph.E;
int[] dist = new int[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i = 0; i < V; ++i)
dist[i] = int.MaxValue;
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 (int i = 1; i < V; ++i) {
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != int.MaxValue && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
// 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 (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) {
Console.WriteLine("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
}
// A utility function used to print the solution
void printArr(int[] dist, int V)
{
Console.WriteLine("Vertex Distance from Source");
for (int i = 0; i < V; ++i)
Console.WriteLine(i + "\t\t" + dist[i]);
}
// Driver method to test above function
public static void Main()
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
Graph graph = new Graph(V, E);
// add edge 0-1 (or A-B in above figure)
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
// add edge 1-4 (or B-E in above figure)
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
graph.BellmanFord(graph, 0);
}
// This code is contributed by Ryuga
}
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1
Notas:
- Los pesos negativos se encuentran en varias aplicaciones de gráficos. Por ejemplo, en lugar de pagar el costo de un camino, podemos obtener alguna ventaja si seguimos el camino.
- Bellman-Ford funciona mejor (mejor que el de Dijkstra) para sistemas distribuidos. A diferencia de Dijkstra, donde necesitamos encontrar el valor mínimo de todos los vértices, en Bellman-Ford, los bordes se consideran uno por uno.
- Bellman-Ford no funciona con gráficos no dirigidos con bordes negativos, ya que se declarará como un ciclo negativo.
Ejercicio:
- El algoritmo estándar de Bellman-Ford informa la ruta más corta solo si no hay ciclos de peso negativos. Modifíquelo para que reporte distancias mínimas aunque haya un ciclo de peso negativo.
- ¿Podemos usar el algoritmo de Dijkstra para las rutas más cortas para gráficos con pesos negativos? Una idea puede ser, para calcular el valor de peso mínimo, agregar un valor positivo (igual al valor absoluto del valor de peso mínimo) a todos los pesos y ejecutar el algoritmo de Dijkstra para el gráfico modificado. ¿Funcionará este algoritmo?
Algoritmo Bellman Ford (implementación simple)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA