02
Bellman-Ford / limited stops (Shortest Paths (Weighted) Sub-pattern)
Cheapest route with a limit on how many edges it may use (or with negative weights).
Signals in the problem statement
- ›
"with at most k stops"
- ›
"negative weights" / "detect a negative cycle"
What makes it different
Cheapest Flights Within K Stops is the template with K + 1 rounds. The copy of dist per round is what enforces the limit; relaxing in place lets a route grow several edges in one round.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Cheapest Flights Within K StopsWalkthroughMediumBasic Anchor·LeetCode #787
Template
bellman-ford-template.cpp
// Bellman-Ford with at most k edges: round i finds every shortest path that uses <= i edges.
// Cheapest Flights Within K Stops = at most k + 1 edges.
int cheapestWithinEdges(int n, const vector<vector<int>>& edges, int src, int dst, int maxEdges) { // edges {u, v, w}
const int INF = INT_MAX;
vector<int> dist(n, INF);
dist[src] = 0;
for (int round = 0; round < maxEdges; round++) {
vector<int> next = dist; // copy: this round may only extend LAST round's paths
for (auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] != INF && dist[u] + w < next[v]) next[v] = dist[u] + w;
}
dist = next;
}
return dist[dst] == INF ? -1 : dist[dst];
}Remember this · Shortest Paths (Weighted)
Trigger
Weighted edges, "minimum cost / time / effort", at most K stops, negative weights, all-pairs distances.
Think
Are edge weights non-negative (Dijkstra), limited by stops (Bellman-Ford), or do I need every pair (Floyd)?
Key question
What is a node's "distance", and when is it final?