Where it runs
1. The problem
Step 97 gave you Dijkstra: the fast way to find shortest paths in a weighted graph. It has one rule, though: every edge weight must be zero or more. Dijkstra fixes a node's distance the moment it takes the node off the heap and never comes back to it. That is safe only when no later edge can make a path cheaper. A negative edge breaks that. A road reached late could still lower a distance, and Dijkstra has already moved on.
So you have a directed graph where some edges cost a negative amount (a discount, a refund, a credit). You still want the shortest distance from one start node to every other node. You also want to know when the question has no answer at all. If you can go around a set of edges whose weights add up to less than zero, every lap makes the total cheaper, without end, and "shortest" stops meaning anything.
Bellman-Ford answers both. It handles negative edges, and it tells you when a negative loop you can reach leaves the task without an answer.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Shortest path problems with negative edges, or with a limit on how many edges a path may use. Bellman-Ford relaxes every edge in rounds, and after k rounds every path of up to k edges is settled.
Run exactly k + 1 rounds and relax from a copy of the previous round's distances, so a path never uses more flights than allowed.
Dijkstra is the usual route, and with n at most 100 the lesson's bellmanFord passes too.
- 1334.Find the City With the Smallest Number of Neighbors at a Threshold Distance (opens in a new tab)Medium
Run Bellman-Ford from every city and stop a run early when a round changes nothing, then count the cities within the threshold.