¿Qué es el Algoritmo de Bellman-Ford?

El Algoritmo de Bellman-Ford es un método para encontrar las distancias más cortas desde un vértice inicial a todos los demás vértices en un grafo ponderado. Es capaz de manejar aristas con pesos negativos y puede detectar ciclos negativos en el grafo.

El Código

                
class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.edges = [];
  }

  addEdge(source, destination, weight) {
    this.edges.push({ source, destination, weight });
  }

  bellmanFord(start) {
    const distances = Array(this.vertices).fill(Infinity);
    distances[start] = 0;

    for (let i = 0; i < this.vertices - 1; i++) {
      for (const { source, destination, weight } of this.edges) {
        if (
          distances[source] !== Infinity &&
          distances[source] + weight < distances[destination]
        ) {
          distances[destination] = distances[source] + weight;
        }
      }
    }

    for (const { source, destination, weight } of this.edges) {
      if (
        distances[source] !== Infinity &&
        distances[source] + weight < distances[destination]
      ) {
        console.log("El grafo contiene un ciclo de peso negativo");
        return;
      }
    }

    return distances;
  }
}

// Ejemplo de uso
const graph = new Graph(5);
graph.addEdge(0, 1, -1);
graph.addEdge(0, 2, 4);
graph.addEdge(1, 2, 3);
graph.addEdge(1, 3, 2);
graph.addEdge(1, 4, 2);
graph.addEdge(3, 2, 5);
graph.addEdge(3, 1, 1);
graph.addEdge(4, 3, -3);

const distances = graph.bellmanFord(0);
console.log("Distancias desde el vértice 0:", distances);
                
            

Puntos Clave del Algoritmo

• Entrada: Un grafo ponderado, con un vértice inicial.
• Salida: Un arreglo con las distancias más cortas desde el vértice inicial a todos los demás.
• Método:
  • Inicializa las distancias a infinito, excepto la del vértice inicial, que es 0.
  • Relaja todas las aristas V-1 veces, donde V es el número de vértices.
  • Verifica la existencia de ciclos negativos recorriendo las aristas una vez más.
• Complejidad:
  • Tiempo: O(V * E), donde V es el número de vértices y E el número de aristas.
  • Espacio: O(V), para almacenar las distancias.
• Ventajas: Puede manejar aristas con pesos negativos.
• Desventajas: Es más lento que Dijkstra y otros algoritmos para grafos densos o sin pesos negativos.

Ejemplo de Ejecución

Grafo inicial:

• Vértices: 0, 1, 2, 3, 4.
• Aristas: [0->1 (-1), 0->2 (4), 1->2 (3), 1->3 (2), 1->4 (2), 3->2 (5), 3->1 (1), 4->3 (-3)].

Proceso del algoritmo:

1. Inicializa las distancias: [0, ∞, ∞, ∞, ∞].
2. Iteración 1: Relaja las aristas y actualiza distancias: [0, -1, 4, ∞, ∞].
3. Iteración 2: Continúa relajando: [0, -1, 2, 1, 1].
4. Iteración 3: Repite hasta completar las V-1 iteraciones.
5. Comprueba ciclos negativos: No se detectan en este caso.

Distancias finales desde el vértice 0:

                [0, -1, 2, 1, 1]
            

Información Adicional

El algoritmo de Bellman-Ford es ampliamente utilizado en redes y sistemas donde los costos o pesos pueden ser negativos. Su capacidad para detectar ciclos negativos lo hace ideal para problemas donde estos ciclos pueden causar problemas.