Shortest path algorithms Flashcards
(21 cards)
What is the goal of shortest path algorithms?
To find the minimum total weight path between nodes in a weighted graph.
What data structure is commonly used to implement sparse graphs?
An adjacency list.
What data structure is good for dense graphs or fast edge lookups?
An adjacency matrix.
What assumption does Dijkstra’s algorithm require?
All edge weights must be non-negative.
What does d(u) represent in Dijkstra’s algorithm?
The current best-known estimate of the shortest path from source to u.
What is δ(u) in Dijkstra’s algorithm?
The true shortest distance from the source node to u.
What is the invariant in Dijkstra’s algorithm?
When a node is added to the settled set S, d(u) = δ(u).
What does edge relaxation mean in Dijkstra’s algorithm?
Updating d(v) if a better path to v is found through u.
How does Dijkstra’s algorithm select the next node to process?
It selects the node in the priority queue with the smallest d(u).
How do you reconstruct a path in Dijkstra’s algorithm?
Keep track of which node each one came from during relaxation, then trace backward.
What is the time complexity of Dijkstra’s algorithm with a heap?
Θ((|V| + |E|) log |V|)
What is the time complexity of Dijkstra with linear search?
Θ(|E| + |V|²)
Can Dijkstra’s algorithm handle negative edge weights?
No — it assumes all weights are non-negative.
What does the Floyd-Warshall algorithm compute?
The shortest paths between all pairs of vertices.
What principle does the Floyd-Warshall algorithm use?
Dynamic programming and the principle of optimality.
What is the recurrence used in Floyd-Warshall?
δ(i, j, k) = min(δ(i, j, k-1), δ(i, k, k-1) + δ(k, j, k-1))
What is the time complexity of Floyd-Warshall?
Θ(n³), where n is the number of vertices.
Is Floyd-Warshall suitable for negative edge weights?
Yes, as long as there are no negative cycles.
How does dynamic programming differ from divide and conquer?
Dynamic programming solves overlapping subproblems with memoization; divide and conquer splits into disjoint problems.
Name one real-world application of Dijkstra’s algorithm.
GPS routing or shortest path planning in maps.
What is matrix exponentiation useful for in graph theory?
Counting paths of fixed lengths (e.g., A² gives number of 2-step paths).
