Bellman-Ford Algorithm

Given a weighted, directed graph with **n** vertices (edge weights may be **negative**) and a source vertex, return the shortest distances from the source to every vertex using the **Bellman-Ford algorithm**. If the graph contains a **negative-weight cycle** reachable from the source, return `null`.

Examples

Input: n = 3, edges = [[0,1,1],[1,2,-1],[2,0,-1]], src = 0

Output: null

The cycle 0→1→2→0 has total weight -1, a negative cycle.

Input: n = 3, edges = [[0,1,4],[0,2,5],[1,2,-3]], src = 0

Output: [0,4,1]

Shortest path to 2 is via 1: 4 + (-3) = 1.

Constraints

• 1 <= n <= 1000
• Edge weights can be negative
• edges[i] = [u, v, weight]

Complexity Analysis

Time

O(V * E)

relax all edges V-1 times, then one more pass to detect negative cycles.

Space

O(V) for the distance array.

Test Cases

#1 — Negative edge, no negative cycle

Input: n=3 edges=[[0,1,4],[0,2,5],[1,2,-3]] src=0

Expected: [0,4,1]

#2 — Negative cycle detected

Input: n=3 edges=[[0,1,1],[1,2,-1],[2,0,-1]] src=0

Expected: null

#3 — Simple positive edge

Input: n=2 edges=[[0,1,5]] src=0

Expected: [0,5]

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.