Skip to main content
Code ScholarsCodeScholars

Graphs and Network Algorithms · Shortest Paths

Bellman Ford's Algorithm

Bellman-Ford relaxes edges repeatedly, handling negative weights and detecting negative cycles.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

We teach this after Dijkstra so students can compare the tradeoff between flexibility and speed.

Guided Lesson Notes

Understanding Bellman Ford's Algorithm

Bellman Ford's Algorithm focuses on relationships, reachability, paths, cycles, connectivity, and optimization over edges. Bellman-Ford relaxes edges repeatedly, handling negative weights and detecting negative cycles.

Model: draw vertices as dots and edges as connections; then decide whether direction, weight, or capacity matters.

Invariant: visited, distance, parent, component, or flow arrays must match what has actually been discovered so far.

Implementation: adjacency lists or matrices, queues, stacks, priority queues, union-find, and repeated edge relaxation.

Use Bellman Ford's Algorithm when the problem mentions roads, networks, prerequisites, components, shortest paths, spanning costs, or dependency order.

Visual Model

A small picture for Bellman Ford's Algorithm

ABCDE

Key Ideas

  • Edge relaxation
  • Negative-weight support
  • Cycle detection

Practice Prompts

  • Trace one full relaxation pass over all edges.
  • Explain what a negative cycle means for shortest paths.

Vocabulary

Terms students should be able to say clearly

Vertex

An object or state in the graph.

Edge

A relationship or move between vertices.

Path

A sequence of edges from one vertex to another.

Cycle

A path that returns to a previous vertex.

Component

A group of vertices connected by reachability.

Relaxation

Trying to improve a known distance or cost through an edge.

Worked Example

Worked example: tracing Bellman Ford's Algorithm

Trace a small input, focusing on edge relaxation.

  1. 1Write a small input where Bellman Ford's Algorithm is clearly useful.
  2. 2Label the part of the input related to Edge relaxation.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Adjacency-list traversalO(V + E)DFS and BFS visit vertices and inspect edges.
Adjacency matrix storageO(V^2)A matrix reserves space for every possible pair.
Weighted optimizationVariesMST and shortest-path algorithms depend on sorting, heaps, and graph density.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Bellman Ford's Algorithm interview problem: Cheapest Route With Limited Stops

Interview medium-hard

Problem

Given directed flight prices, find the cheapest cost from source to target using at most k intermediate stops.

Input

The first line contains n, m, source, target, and k. The next m lines contain u v cost.

Output

Print the cheapest cost, or -1 if no allowed route exists.

Sample Input

4 5 0 3 1
0 1 100
1 2 100
2 3 100
0 2 500
1 3 600

Sample Output

600

Why the sample works

With at most one stop, route 0->2->3 costs 600 and is cheaper than 0->1->3 at 700.

Approach

  1. 1A route with at most k stops uses at most k + 1 edges.
  2. 2Run k + 1 rounds of Bellman-Ford-style relaxation.
  3. 3Copy the previous distance array each round so a round uses exactly one more edge.
  4. 4The target distance after the final round is the answer.

O(km) time and O(n) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int source = sc.nextInt();
    int target = sc.nextInt();
    int k = sc.nextInt();

    int[][] edges = new int[m][3];
    for (int i = 0; i < m; i++) {
      edges[i][0] = sc.nextInt();
      edges[i][1] = sc.nextInt();
      edges[i][2] = sc.nextInt();
    }

    int inf = 1_000_000_000;
    int[] dist = new int[n];
    Arrays.fill(dist, inf);
    dist[source] = 0;

    for (int round = 0; round <= k; round++) {
      int[] next = dist.clone();
      for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int cost = edge[2];
        if (dist[u] != inf && dist[u] + cost < next[v]) {
          next[v] = dist[u] + cost;
        }
      }
      dist = next;
    }

    System.out.println(dist[target] == inf ? -1 : dist[target]);
  }
}

Python Solution

n, m, source, target, k = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

INF = 10 ** 18
dist = [INF] * n
dist[source] = 0

for _ in range(k + 1):
    nxt = dist[:]
    for u, v, cost in edges:
        if dist[u] != INF and dist[u] + cost < nxt[v]:
            nxt[v] = dist[u] + cost
    dist = nxt

print(-1 if dist[target] == INF else dist[target])

Practice Challenge

Make the idea your own

Create a two-minute explanation of Bellman Ford's Algorithm: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler