Bellman-Ford & Floyd-Warshall

While Dijkstra's algorithm is fast and efficient for finding shortest paths, it fundamentally breaks if the graph contains negative edge weights. For graphs with financial transactions, chemical reactions, or arbitrage scenarios where weights can be negative, we must use alternative algorithms.

1. Bellman-Ford Algorithm

Bellman-Ford finds the shortest path from a Single Source to all other vertices. It is slower than Dijkstra's, but it perfectly handles negative weights.

More importantly, Bellman-Ford can detect Negative Weight Cycles—a loop in the graph where the sum of the edges is negative. If a negative cycle exists, you can loop through it infinitely to achieve a path distance of $-\infty$, meaning a true "shortest path" mathematically cannot exist.

How it Works (Dynamic Programming / Relaxation)

Instead of greedily picking the closest node, Bellman-Ford brutally iterates over all edges in the graph $V - 1$ times.

In a graph with $V$ vertices, the longest possible path without cycles can have at most $V - 1$ edges. By relaxing every single edge $V - 1$ times, the shortest path is guaranteed to propagate throughout the entire graph.

// Edge list representation is easier for Bellman-Ford
interface Edge {
  u: number; // Source
  v: number; // Destination
  w: number; // Weight
}

function bellmanFord(edges: Edge[], numVertices: number, start: number): number[] {
  const distances = new Array(numVertices).fill(Infinity);
  distances[start] = 0;

  // Step 1: Relax all edges (V - 1) times
  for (let i = 0; i < numVertices - 1; i++) {
    for (const { u, v, w } of edges) {
      if (distances[u] !== Infinity && distances[u] + w < distances[v]) {
        distances[v] = distances[u] + w;
      }
    }
  }

  // Step 2: Check for Negative Weight Cycles
  // If we run the relaxation ONE MORE TIME and a distance updates,
  // it proves there is a negative infinite loop!
  for (const { u, v, w } of edges) {
    if (distances[u] !== Infinity && distances[u] + w < distances[v]) {
      throw new Error("Graph contains a negative-weight cycle!");
    }
  }

  return distances;
}

• Time Complexity: $O(V \times E)$
• Space Complexity: $O(V)$

2. Floyd-Warshall Algorithm

What if we don't just want the distance from a single start node, but we want the shortest path between All Pairs of nodes? You could run Dijkstra's algorithm $V$ times (once from every node), but if there are negative weights, you must use Floyd-Warshall.

Floyd-Warshall is an elegant Dynamic Programming algorithm that relies on an Adjacency Matrix representation.

How it Works

The algorithm checks, for every pair of nodes (i, j), if there is an intermediate node k that offers a shorter path than going directly from i to j.

If Distance(i -> k) + Distance(k -> j) < Distance(i -> j), we update the matrix!

function floydWarshall(matrix: number[][]): number[][] {
  const V = matrix.length;
  // Clone the adjacency matrix to act as our DP table
  // Assume matrix[i][j] = Infinity if no edge exists, and 0 if i === j
  const dist = matrix.map(row => [...row]);

  // The outer loop picks every vertex one by one as an intermediate node
  for (let k = 0; k < V; k++) {
    // Pick all vertices as source one by one
    for (let i = 0; i < V; i++) {
      // Pick all vertices as destination for the above source
      for (let j = 0; j < V; j++) {
        
        // If vertex k is on the shortest path from i to j, update it!
        if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
        
      }
    }
  }

  return dist;
}

• Time Complexity: $O(V^3)$. Because of the triple nested loop, this algorithm is incredibly slow and only viable for very small graphs (e.g., $V \le 400$).
• Space Complexity: $O(V^2)$ to store the 2D distance matrix.