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

Recall & Review

beginner

What is a Directed Acyclic Graph (DAG)?

A Directed Acyclic Graph (DAG) is a graph with directed edges and no cycles, meaning you cannot start at one node and follow a path that leads back to the same node.

intermediate

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

Topological order arranges nodes so that all edges go from earlier to later nodes. This order helps us relax edges only once, making shortest path calculation efficient in DAGs.

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.

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.

beginner

In the context of shortest path in DAG, what initial distance values do we assign before processing?

We assign 0 to the source node and infinity (or a very large number) to all other nodes to indicate they are initially unreachable.

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

A It must be a Directed Acyclic Graph (DAG)

B It must be undirected

C It must contain cycles

D It must be a tree

Only DAGs have a valid topological order because they have no cycles.

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

A Relax all edges randomly

B Find the topological order of the graph

C Initialize 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, how many times is each edge relaxed?

A Once

B Multiple times

C Never

D Depends on the graph size

Each edge is relaxed exactly once in topological order, making the algorithm efficient.

What initial distance is assigned to the source node before starting the algorithm?

A -1

B Infinity

C 0

D Number of nodes

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

What happens if the graph contains a cycle when trying to find shortest path using topological order?

A Edges are ignored

B Algorithm runs normally

C Shortest path is found faster

D Topological order does not exist, so the method fails

Topological order requires no cycles; if cycles exist, the method cannot be applied.

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

Think about how ordering nodes prevents revisiting edges multiple times.

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

Start with distance setup, then order, then edge relaxation.