SimuVedaAlgorithms Lab Open in the lab

Graphs / Advanced

Bellman-Ford Shortest Path Visualizer

Relax every edge, V − 1 times. After round i, every shortest path that uses at most i edges is correct. One more round that still improves something means a negative cycle.

Start the Bellman-Ford Shortest Path simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(V·E)
Average timeO(V·E)
Worst timeO(V·E)
Extra spaceO(V)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Every distance starts at ∞, except A which is 0.
  2. Round 1: try every edge once.
  3. A→B: 0 + (4) = 4, better than ∞. Update B.
  4. A→C: 0 + (5) = 5, better than ∞. Update C.
  5. C→B: 5 + (-3) = 2, better than 4. Update B.
  6. B→D: 2 + (3) = 5, better than ∞. Update D.
  7. C→E: 5 + (6) = 11, better than ∞. Update E.
  8. D→E: 5 + (2) = 7, better than 11. Update E.
  9. D→F: 5 + (4) = 9, better than ∞. Update F.
  10. E→F: 7 + (-1) = 6, better than 9. Update F.
  11. Round 2: try every edge once.
  12. A→B: 0 + (4) = 4, not better than 2.
  13. A→C: 0 + (5) = 5, not better than 5.
  14. C→B: 5 + (-3) = 2, not better than 2.
  15. B→D: 2 + (3) = 5, not better than 5.
  16. C→E: 5 + (6) = 11, not better than 7.
  17. D→E: 5 + (2) = 7, not better than 7.
  18. D→F: 5 + (4) = 9, not better than 6.
  19. E→F: 7 + (-1) = 6, not better than 6.
  20. Nothing changed in round 2, so later rounds can’t change anything either. (Real code often stops here.)
  21. Final check passed: no negative cycle. Distances from A: A 0, B 2, C 5, D 5, E 7, F 6.

Try it with your own input →

Bellman-Ford shortest path in Java, Python, C++, C and JavaScript

int[] bellmanFord(int src) {
  int[] dist = new int[n]; fill(dist, INF);
  dist[src] = 0;
  for (int i = 1; i < n; i++) {
    for (Edge e : edges) {
      if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
        dist[e.v] = dist[e.u] + e.w;
    }
  }
  for (Edge e : edges)
    if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
      throw new IllegalStateException("negative cycle");
  return dist;
}
def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(1, n):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError("negative cycle")
    return dist
struct Edge { int u, v, w; };

vector<int> bellmanFord(int n, const vector<Edge>& edges, int src) {
  vector<int> dist(n, INT_MAX);
  dist[src] = 0;
  for (int i = 1; i < n; i++) {
    for (const Edge& e : edges) {
      if (dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v])
        dist[e.v] = dist[e.u] + e.w;
    }
  }
  for (const Edge& e : edges)
    if (dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v])
      throw runtime_error("negative cycle");
  return dist;
}
#include <limits.h>
struct Edge { int u, v, w; };

/* returns 0 if there is a negative cycle */
int bellmanFord(int n, struct Edge edges[], int m, int src, int dist[]) {
  for (int i = 0; i < n; i++) dist[i] = INT_MAX;
  dist[src] = 0;
  for (int i = 1; i < n; i++) {
    for (int k = 0; k < m; k++) {
      struct Edge e = edges[k];
      if (dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v])
        dist[e.v] = dist[e.u] + e.w;
    }
  }
  for (int k = 0; k < m; k++)
    if (dist[edges[k].u] != INT_MAX && dist[edges[k].u] + edges[k].w < dist[edges[k].v])
      return 0;  // negative cycle
  return 1;
}
function bellmanFord(n, edges, src) {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  for (let i = 1; i < n; i++) {
    for (const { u, v, w } of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v])
        dist[v] = dist[u] + w;
    }
  }
  for (const { u, v, w } of edges)
    if (dist[u] !== Infinity && dist[u] + w < dist[v])
      throw new Error('negative cycle');
  return dist;
}

In an interview

LeetCode 787, Cheapest Flights Within K Stops, is Bellman-Ford limited to K + 1 rounds. 743 Network Delay Time works too.

Add E>C -5 to the example to make a negative cycle and watch the final check catch it. Dijkstra would silently give a wrong answer.

More graphs