Dijkstra’s Algorithm for Single Source Shortest Paths with Nonnegative Edge Weights Flashcards
What is the main purpose of Dijkstra’s Algorithm?
To find the shortest path from a source node to all other nodes in a graph with non-negative edge weights.
What type of graph can Dijkstra’s Algorithm be applied to?
Graphs with non-negative edge weights, possibly with cycles, but no negative weights.
What type of algorithm is Dijkstra’s?
It is a greedy algorithm.
What key data structure is used in Dijkstra’s Algorithm?
Min-priority queue (heap) keyed by distance estimates (d-values).
What is the relaxation condition in Dijkstra’s Algorithm?
If u.d + w(u,v) < v.d, then update v.d = u.d + w(u,v) and v.π = u.
What is the initialization step in Dijkstra’s Algorithm?
Set source.d = 0 and all other vertex.d = ∞, vertex.π = NIL.
How does the main loop of Dijkstra’s Algorithm operate?
Extract the node with smallest d-value from heap, then relax all its outgoing edges.
What does ‘extract_min’ do in the priority queue?
It removes and returns the vertex with the smallest distance estimate.
Why do we call Dijkstra’s Algorithm greedy?
Because it always selects the node with the current smallest d-value.
How many times is each edge relaxed in Dijkstra’s Algorithm?
Exactly once.
What is the time complexity of Dijkstra’s Algorithm using a min-heap?
O((m + n) log n), where n is the number of vertices and m is the number of edges.
Why is Dijkstra’s Algorithm faster than Bellman-Ford?
Because each edge is relaxed once and it uses a priority queue for efficient node selection.
Can Dijkstra’s Algorithm handle negative weight edges?
No, it only works with non-negative weights.
What happens when a node’s d-value is updated?
It must be bubbled up in the heap using decrease_key.
What is stored in each vertex during the algorithm?
Its current distance estimate (d) and its parent node (π).
What is the main goal of the proof of Dijkstra’s Algorithm?
To show that Dijkstra’s Algorithm correctly computes shortest paths from a source node to all other nodes.
What is the key invariant in Dijkstra’s Algorithm?
For every vertex v in the processed set P, v.d equals the shortest path distance from source s to v.
What is set P in the context of Dijkstra’s Algorithm?
P is the set of vertices that have been removed from the priority queue and fully processed.
What does the proof use to establish correctness?
Mathematical induction on the number of times the main loop executes.
What is the base case for the induction proof?
When the source node s is first chosen, s.d = 0 = δ(s, s), so the invariant holds.
What is assumed in the inductive hypothesis?
That for all vertices in P, v.d = δ(s, v).
What must be proven in the inductive step?
That for the next chosen node u (with smallest d in V-P), u.d = δ(s, u).
Why is u.π always in the processed set P?
Because edges are only relaxed from processed vertices, so u’s parent must have been processed.
What contradiction does the proof use?
It assumes there is a shorter path to u through w ∈ P, but that would imply u.d is not the smallest, contradicting its selection.
