PPractick

The problem

A currency-exchange analyser models conversion costs as a directed graph whose weights can be negative (rebates), and needs shortest costs from a source. Dijkstra breaks with negative weights, so use Bellman–Ford. Relax every edge V − 1 times: a shortest path uses at most V − 1 edges, so after that many rounds every distance is correct. If a V-th round still improves something, a negative cycle is reachable, and shortest paths aren't defined.

Example: 3 vertices, edges 0→1 (5), 1→0 (3), 1→2 (−1), 2→0 (1), source 2 → [1, 6, 0].

Function signature

vector<int> bellmanFord(int V, const vector<array<int, 3>>& edges, int S);
// unreachable -> 100000000; a negative cycle reachable from S -> {-1}

Test cases

Input (V, edges, S)	Output	Explanation
(3, [[0,1,5],[1,0,3],[1,2,-1],[2,0,1]], 2)	[1, 6, 0]
(2, [[0,1,9]], 0)	[0, 9]
(3, [[0,1,-2]], 0)	[0, -2, 100000000]	2 is unreachable
(3, [[0,1,1],[1,2,-3],[2,0,1]], 0)	[-1]	The cycle weight is −1
(1, [], 0)	[0]

(Confirm: directed edges; weights may be negative; 10⁸ marks unreachable; the negative-cycle check only considers cycles reachable from S.)

How interviewers phrase it

• "Find the shortest distance from source S to every vertex in a weighted directed graph with possibly negative edges; if a negative cycle exists, return [−1]" (GeeksforGeeks "Distance from the Source (Bellman-Ford Algorithm)").

Clarifying questions to ask

1. Can weights be negative? (Yes, which is the reason to use Bellman–Ford.)
2. What about unreachable vertices? (10⁸.)
3. Which negative cycles count? (Those reachable from S, since only they affect distances.)

Follow-ups to expect

1. "Why V − 1 rounds?"
2. "How is a negative cycle detected?"
3. "Why skip unreachable sources when relaxing?"
4. "Why prefer it over Dijkstra sometimes?"
5. "Complexity?"

Related questions

• Cheapest flight within K stops Hard
• M Coloring Problem Hard
• Celebrity Problem Hard
• Cycle Detection in Undirected Graph (bfs) Hard
• Detect a cycle in an undirected graph Hard
• Word ladder I Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in