Shortest Path in DAG Using Topological Order in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Directed Acyclic Graph (DAG)?

A DAG is a graph with directed edges and no cycles, meaning you cannot start at one node and follow a path that loops back to the same node.

intermediate

Why do we use topological order for shortest path in a DAG?

Topological order arranges nodes so all edges go from earlier to later nodes, allowing us to relax edges in one pass without revisiting nodes, making shortest path calculation efficient.

beginner

What does 'relaxing an edge' mean in shortest path algorithms?

Relaxing an edge means checking if the current known shortest distance to a node can be improved by going through another node connected by that edge, and updating it if yes.

beginner

In the shortest path algorithm for DAG, what initial distance values do we assign to nodes?

We set the source node distance to 0 and all other nodes to infinity (or a very large number) to indicate they are not yet reachable.

intermediate

What is the time complexity of finding shortest paths in a DAG using topological order?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each node and edge is processed once.

What property must a graph have to use topological order for shortest path?

A It must be a complete graph

B It must be an undirected graph

C It must contain cycles

D It must be a Directed Acyclic Graph (DAG)

Topological order only exists for DAGs because cycles prevent a linear ordering.

What is the first step in finding shortest paths in a DAG using topological order?

A Find the topological order of the graph

B Relax all edges randomly

C Set all distances to zero

D Run Dijkstra's algorithm

We first find the topological order to process nodes in a sequence that respects edge directions.

When relaxing edges in shortest path for DAG, what do we update?

A The distance to the target node if a shorter path is found

B The number of edges in the graph

C The topological order

D The source node

Relaxing updates the shortest known distance to a node if a better path is found.

What initial distance is assigned to the source node in shortest path calculation?

A Infinity

B -1

C 0

D 1

The source node distance is set to 0 because the distance from source to itself is zero.

What is the advantage of using topological order for shortest path in DAG over Dijkstra's algorithm?

A It works with negative cycles

B It runs faster with O(V + E) time complexity

C It uses more memory

D It requires no initialization

Topological order allows processing each node once, making it faster than Dijkstra's O(E log V) in DAGs.

Explain how topological order helps in finding the shortest path in a DAG.

Think about how ordering nodes prevents revisiting.

Describe the steps to find shortest paths from a source node in a DAG using topological order.

Start from ordering, then update distances step by step.