28. Bellman-Ford

PRO

Hard

Topics

Helpful tools to learn & understand

Watch key transitions, pointers, and variables update step-by-step.

Open

Read clean, documented implementations across multiple patterns.

View Code

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1

Output: 700

Explanation: The cheapest path from city 0 to city 3 with at most 1 stop is 0 -> 1 -> 3 with a cost of 100 + 600 = 700.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

Output: 200

Explanation: The cheapest path from city 0 to city 2 with at most 1 stop is 0 -> 1 -> 2 with a cost of 100 + 100 = 200.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Output: 500

Explanation: The cheapest path from city 0 to city 2 with at most 0 stops is 0 -> 2 with a cost of 500.

Time Complexity

O(VE)

Space Complexity

O(V)