Bellman-Ford Shortest Path Problem

Bellman-Ford Shortest Path Problem — ExecCode Medium DSA Practice

Solve the Bellman-Ford Shortest Path problem on ExecCode. Free online medium DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Compute single-source shortest paths on a directed graph that may contain negative edge weights. After |V|-1 relaxations, run one more pass: if any distance still improves, return -1 (negative cycle); otherwise return the dist array.

Examples

Input n = 6, edges = [[0, 1, 4], [0, 2, 5], [1, 2, -3], [2, 3, 4], [3, 4, 2], [1, 4, 8], [4, 5, -1]], src = 0; Output [0, 4, 1, 5, 7, 6]. Input n = 3, edges = [[0, 1, 1], [1, 2, -1], [2, 1, -1]], src = 0; Output -1

Constraints

1 ≤ n ≤ 500 0 ≤ edges.length ≤ n*(n-1) Weights may be negative 0 ≤ src < n

Practice Bellman-Ford Shortest Path free on ExecCode. Browse DSA problems, topic map, and placement guides.