En la entrada anterior vimos la implementación del algoritmo de Dijkstra para calcular distancias cortas entre los nodos de un grafo. En esta ocasión vamos a revisar el algoritmo Bellman-Ford.
El algoritmo de Bellman-Ford es un algoritmo de búsqueda de caminos más cortos en un grafo que puede manejar aristas con pesos negativos, a diferencia del algoritmo de Dijkstra. Sin embargo, el algoritmo de Bellman-Ford es menos eficiente que el algoritmo de Dijkstra y tiene una complejidad de tiempo de O(V ⋅ E), donde V es el número de nodos y E es el número de aristas en el grafo.
Pseudocódigo del algoritmo
- Inicializar las distancias a todos los nodos como infinito, excepto el nodo de origen que se inicializa como 0.
- Para cada nodo en el grafo:
- Para cada arista (u, v) en el grafo:
- Si distancia[u] + peso(u, v) < distancia[v], actualizar distancia[v] = distancia[u] + peso(u, v).
- Para cada arista (u, v) en el grafo:
- Repetir el paso 2 para un total de V-1 veces (V es el número de nodos en el grafo).
- Verificar si hay ciclos de peso negativo:
- Para cada arista (u, v) en el grafo:
- Si distancia[u] + peso(u, v) < distancia[v], entonces hay un ciclo de peso negativo en el grafo.
- Para cada arista (u, v) en el grafo:
- Las distancias finales representan los caminos más cortos desde el nodo de origen a todos los demás nodos en el grafo.
Definición del código del algoritmo
De manera similar que el algoritmo de Dijkstra, para este ejemplo vamos a trabajar con clases de Python, así que lo primero que haremos será definir los métodos de la clase (Graph) para luego presentar el código completo de la misma.
Método __init__
Cómo vimos anteriormente, cuando se trabaja con clases en Python, es común definir el método __init__(self) para inicializar la instancia del objeto con valores que se requieran. De igual manera, en este caso vamos a inicializar la instancia con dos atributos, un conjunto para almacenar los nodos y un conjunto para almacenar las aristas.
def __init__(self):
self.nodes = set()
self.edges = set()
Método para agregar nodos
Este método recibe como parámetro el valor del nodo que se quiere agregar y lo inserta en el atributo nodes que definimos en el método __init__.
Nota: La idea de que los nodos sean un objeto del tipo set() es porque deben ser únicos y no deben existir nodos duplicados.
def addNode(self, value):
self.nodes.add(value)
Método para agregar aristas
El método para agregar aristas a más del parámetro self recibe tres parámetros, origin para referirse al nodo de origen, destiny correspondiente al nodo de destino y weight que hace referencia al peso de la arista desde el origen hasta el destino. Con estos parámetros se crea una tupla que se va a agregar en el atributo edges de tipo set (conjunto) de la clase.
def addEdge(self, origin, destiny, weight):
self.edges.add((origin, destiny, weight))
Método del algoritmo de Bellman-Ford
Para este método se requiere como parámetro el nodo de inicio desde donde se va a calcular las distancias. Con este valor ejecutamos los pasos definidos en el pseudocódigo de la siguiente manera:
def bellman_ford(self, inicio):
# Paso 1: Inicializamos las distancias
distancias = {nodo: float('infinity') for nodo in self.nodos}
distancias[inicio] = 0
# Paso 2: Ejecutamos la relajación de aristas V-1 veces
for _ in range(len(self.nodos) - 1):
for u, v, peso in self.aristas:
if distancias[u] + peso < distancias[v]:
distancias[v] = distancias[u] + peso
# Paso 4: Verificamos los ciclos de peso negativo
for u, v, peso in self.aristas:
if distancias[u] + peso < distancias[v]:
print("El grafo contiene un ciclo de peso negativo")
return
# Las distancias finales representan los caminos más cortos desde el nodo de origen
return distancias
Clase Graph
Con todos los métodos de la clase Graph definidos, vamos a ver cómo quedaría todo junto:
class Graph:
def __init__(self):
self.nodes = set()
self.edges = set()
def addNode(self, value):
self.nodes.add(value)
def addEdge(self, origin, destiny, weight):
self.edges.add((origin, destiny, weight))
def bellman_ford(self, start):
# Paso 1: Inicializar las distancias
distances = {node: float('infinity') for node in self.nodes}
distances[start] = 0
# Paso 2: Relajación de aristas V-1 veces
for _ in range(len(self.nodes) - 1):
for u, v, weight in self.edges:
if distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
# Paso 4: Verificar ciclos de peso negativo
for u, v, weight in self.edges:
if distances[u] + weight < distances[v]:
print("The graph contains a negative weight cycle")
return
# Las distancias finales representan los caminos más cortos desde el nodo de origen
return distances
Probando el funcionamiento
Una vez definida la lógica de la clase Graph, podemos realizar pruebas para validar que la implementación funciona de manera correcta. Para esto, igual que antes lo primero que debemos hacer es crear una instancia de la clase:
graph = Graph()
Con esta instancia creamos los nodos de nuestro grafo de la misma manera que antes, es decir 8 nodos correspondientes a las letras de la A hasta la H.
graph.addNode('A')
graph.addNode('B')
graph.addNode('C')
graph.addNode('D')
graph.addNode('E')
graph.addNode('F')
graph.addNode('G')
graph.addNode('H')
Así mismo creamos las aristas con los mismos valores que en el ejemplo anterior para tener el mismo grafo:
graph.addEdge('A', 'B', 4)
graph.addEdge('A', 'C', 9)
graph.addEdge('A', 'E', 7)
graph.addEdge('A', 'F', 3)
graph.addEdge('A', 'G', 11)
graph.addEdge('A', 'H', 15)
graph.addEdge('B', 'C', 4)
graph.addEdge('B', 'D', 4)
graph.addEdge('B', 'E', 2)
graph.addEdge('B', 'G', 9)
graph.addEdge('C', 'D', 8)
graph.addEdge('C', 'F', 2)
graph.addEdge('D', 'G', 11)
graph.addEdge('D', 'F', 8)
graph.addEdge('D', 'E', 5)
graph.addEdge('D', 'H', 4)
graph.addEdge('E', 'G', 3)
graph.addEdge('E', 'H', 14)
El grafo creado tiene la siguiente estructura:
Ahora debemos definir cuál va a ser nuestro punto de partida y con eso calcular las distancias:
start = 'A'
distances = graph.bellman_ford(start)
Por último vamos a mostrar cuáles son los caminos más cortos desde el nodo de partida A hacia el resto de los nodos, para eso recorremos todos los elementos de las distancias e imprimimos el resultado:
print("Distancias más cortas desde el nodo", start)
for node, distance in distances.items():
print(f"A -> {node}: {distance}")
Y obtenemos el siguiente resultado, que como podemos apreciar nos muestra las mismas distancias que el algoritmo de Dijkstra:
Distancias más cortas desde el nodo A
A -> F: 3
A -> E: 6
A -> G: 9
A -> C: 8
A -> A: 0
A -> D: 8
A -> H: 12
A -> B: 4
