How does the Bellman-Ford algorithm work? | Interview Question

Q: How does the Bellman-Ford algorithm work?

**Target Audience:** Beginners preparing for coding interviews — no graph-algorithm background assumed **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First A group of travel agents each know only the direct ticket prices out of their own city. Every morning, each agent phones the agents in the cities they fly to and says: "I can get a traveller from home to my city for X; add your ticket price and see if that beats what you have." That is one **round**. After the first morning, everyone one flight away from home knows a price. After the second morning, everyone two flights away does, and so on. If there are n cities, no sensible route uses more than n -

The problem

Question presented to candidate: "How does the Bellman-Ford algorithm work? Implement it in Python for a directed graph given as an edge list that may contain negative weights, and tell me how you would detect a negative cycle."

What a strong answer should cover:

Relax every edge V - 1 times; why V - 1 (a shortest simple path has at most V - 1 edges) and the round invariant.
Negative-cycle detection with one extra round, and how to recover the cycle by walking parent V times.
O(V × E) time and O(V) extra space; early exit when a round changes nothing; comparison with Dijkstra.
Only cycles reachable from the source are detected, and the virtual-source trick to find any cycle.
Python specifics: float("inf") absorbs additions so inf + (-5) stays inf, but still guard dist[u] != INF for clarity; iterate a list of (u, v, w) tuples; any() for the detection pass.

Clarifying questions expected:

"Can there be a negative cycle, and should I report it or print it?"
"Is there a limit on the number of edges in a path?"

Code / implementation expected: Yes — a Python bellman_ford(n, edges, source) returning distances and a negative-cycle flag, ideally with early exit.

graphs
shortest-path

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no graph-algorithm background assumed Difficulty: Hard Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

A group of travel agents each know only the direct ticket prices out of their own city. Every morning, each agent phones the agents in the cities they fly to and says: "I can get a traveller from home to my city for X; add your ticket price and see if that beats what you have." That is one round. After the first morning, everyone one flight away from home knows a price. After the second morning, eve

The solution is hidden so you can try first

9 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonBellman-Ford round by round, worst and best edge order

Practice

PythonDetecting and printing a negative cycle

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.