Bellman Ford Algorithm for Single Source Shortest Paths Flashcards
What problem does the Bellman-Ford algorithm solve?
The single-source shortest path problem, even with negative edge weights.
What is the core operation of the Bellman-Ford algorithm?
Edge relaxation: if d[u] + w(u,v) < d[v], then update d[v] and π[v].
How are distances initialized in Bellman-Ford?
d[source] = 0; d[v] = ∞ for all other vertices; π[v] = NIL.
What is the time complexity of Bellman-Ford?
Θ(V * E), where V is number of vertices and E is number of edges.
How many times does Bellman-Ford relax each edge?
At most |V| - 1 times.
What condition signals a negative-weight cycle in Bellman-Ford?
If any edge can still be relaxed after |V| - 1 iterations.
What does the parent pointer π[v] track in Bellman-Ford?
The vertex u that provides the shortest path to v via edge (u,v).
What is the Monotonicity Property of Bellman-Ford?
At all times, d[v] ≥ δ(s, v), where δ(s,v) is the true shortest path length.
After how many iterations are all shortest paths guaranteed (if no negative cycle)?
After |V| - 1 iterations.
What does it mean to ‘relax’ an edge (u,v)?
Check if d[u] + w(u,v) < d[v]; if so, update d[v] and π[v].
What property ensures that Bellman-Ford’s estimate d[v] always reflects a real path?
Existence Property: if d[v] ≠ ∞, then there exists a path from s to v of that length.
What is the behavior of Bellman-Ford in the presence of a negative-weight cycle?
It detects the cycle and declares shortest paths are undefined.
What are the three main steps in Bellman-Ford?
- Initialize distances, 2. Relax all edges |V|-1 times, 3. Check for negative cycles.
