DAG Shortest Path Flashcards
What is a Directed Acyclic Graph (DAG)?
A graph with directed edges and no cycles.
Why can we optimize shortest path algorithms on DAGs?
Because DAGs have no cycles, allowing us to use topological ordering to process vertices efficiently.
What is the key idea for finding shortest paths in DAGs?
Topologically sort the graph, then relax all edges from each vertex in topological order.
What is the time complexity of the shortest path algorithm on a DAG?
Θ(V + E), where V is the number of vertices and E is the number of edges.
What is topological sorting?
An ordering of vertices such that for every directed edge u -> v, vertex u comes before v.
What is the relaxation condition for an edge (u, v) with weight w?
If dist[v] > dist[u] + w, then update dist[v] = dist[u] + w.
How many rounds of relaxation are needed for shortest path in a DAG?
Only one pass through the vertices in topological order.
What is the best algorithm when all edge weights are 1?
Breadth-First Search (BFS).
Why does BFS work when all edge weights are 1?
BFS visits vertices in order of their depth from the source, matching shortest paths by edge count.
What is the time complexity of BFS?
Θ(V + E).
What is the best algorithm when all edge weights are non-negative?
Dijkstra’s algorithm.
When should you use Bellman-Ford?
When the graph may contain negative edge weights.
What does Dijkstra’s algorithm require about edge weights?
All edge weights must be non-negative.
What makes the DAG shortest path method faster than Bellman-Ford?
It uses a single pass and leverages topological order instead of V-1 passes.
What is the first step in DAG shortest path algorithm?
Perform a topological sort of the graph.
What is the second step in DAG shortest path algorithm?
Initialize distances and relax all edges from each vertex in topological order.
