Medium
A Bellman-Ford that stops after V-1 rounds
Bellman-Ford relaxes all E edges once per round. A candidate implementation runs exactly V-1 rounds and then stops, reporting the resulting distances as final, with no further check. What is its time complexity, and what capability does it lack compared to the textbook version?
main.cpp
for (int round = 0; round < V - 1; round++) {
for (auto& [u, v, w] : edges) {
if (dist[u] != INF && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
// stops here: no extra round, no negative-cycle check18 of 46 in Data Structures & Algorithms