Shortest Path Flashcards
Front
Back
What is the shortest path problem?
Given a weighted directed graph, find the path from source s to destination t with the least total weight.
Why is the shortest path problem important?
Used in navigation (Google Maps), logistics (FedEx, UPS), network routing, AI pathfinding in games.
What are the types of shortest path problems?
Single source, All pairs, and Single destination (can be reduced to single source via transpose).
What is the output of a shortest path algorithm?
A cost table (shortest distances) and a parent table (to reconstruct paths).
How do shortest paths relate to tree structures?
All shortest paths from a source form a tree-like structure rooted at that source.
What is the optimal substructure property of shortest paths?
Any subpath of a shortest path is also a shortest path.
How can you recover a path using the parent table?
Trace back from destination using parent pointers until reaching the source.
What is the formula for the weight of a path P = [v0, v1, …, vk]?
Sum of edge weights: weight(P) = ∑ w(vi−1, vi) from i = 1 to k.
What is the effect of positive or zero-weight cycles?
They do not help reduce the path cost and can be safely ignored.
What is the effect of negative-weight cycles?
They make shortest paths undefined or -∞ due to infinite improvements.
How can you detect a negative-weight cycle?
Using Bellman-Ford algorithm by checking for further improvements after n-1 iterations.
What is the general pseudocode pattern for shortest path algorithms?
Initialize distances and parents, relax all edges repeatedly to find shortest paths.
What is stored in the parent table?
The previous vertex on the shortest path to a destination.
How do you reconstruct the path from s to v?
Follow parent pointers from v back to s and reverse the path.
What does it mean to solve a single-destination shortest path problem?
Find shortest paths to one destination from all sources by reversing all edges.
Why is storing only the last path-one node sufficient?
It allows full path reconstruction without storing entire path lists.
Why do negative-weight cycles corrupt shortest path answers?
Because they allow you to loop infinitely and decrease path cost without bound.
What is the ‘foreign taxi’ analogy for negative-weight cycles?
A driver takes you on a long detour charging extra—reflects unpredictable cost inflation.
What data structure can shortest path algorithms use for efficiency?
Priority queues (e.g. in Dijkstra), arrays (Bellman-Ford), or matrices (Floyd-Warshall).
How does dynamic programming apply to shortest path problems?
Use memoization to store shortest costs and reuse sub-results (optimal substructure).
