Dijkstra's Algorithm: Correctness, Implementations, and Variants

All flashcards

Weighted graph

A graph whose edges have costs, such as distance, travel time, or network delay.

Shortest path

A path whose total edge cost is minimal among paths between the same endpoints.

Relaxation

Testing whether a route through a vertex improves a neighbor's tentative distance.

Decrease-key

A priority-queue operation that lowers an item's priority after a better route is found.

Uniform-cost search

A search method closely related to Dijkstra's algorithm.

Quiz questions

1. Given a source vertex, what does Dijkstra's algorithm compute?Answer: Shortest distances from the source to every reachable vertex.
2. During Dijkstra's algorithm, what happens when relaxation finds a route to a neighbor that is shorter than its current estimate?Answer: The neighbor's distance estimate and predecessor are updated.
3. When can a standard Dijkstra search for one destination safely stop?Answer: When the destination is selected as the unvisited vertex with the smallest tentative distance.
4. With adjacency lists and a binary heap, what is a standard time bound for Dijkstra's algorithm?Answer: $O((|V|+|E|)\log |V|)$
5. What problem does Prim's algorithm solve, unlike Dijkstra's algorithm?Answer: Finding a minimum spanning tree.