Shortest Path in DAG Using Topological Order in DSA Typescript - Time & Space Complexity

Time Complexity: Shortest Path in DAG Using Topological Order

O(n + e)

Understanding Time Complexity

We want to understand how long it takes to find the shortest path in a Directed Acyclic Graph (DAG) using topological order.

Specifically, how the time grows as the graph gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function shortestPathDAG(graph: Map<number, Array<[number, number]>>, start: number, n: number): number[] {
  const dist = Array(n).fill(Infinity);
  dist[start] = 0;
  const topoOrder = topologicalSort(graph, n);

  for (const u of topoOrder) {
    if (dist[u] !== Infinity) {
      for (const [v, weight] of graph.get(u) || []) {
        if (dist[u] + weight < dist[v]) {
          dist[v] = dist[u] + weight;
        }
      }
    }
  }
  return dist;
}
    

This code finds shortest distances from a start node to all others in a DAG using topological order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop goes through each node once in topological order.
• Nested operation: For each node, it loops through all its edges (neighbors).
• How many times: Each edge is checked exactly once during the nested loop.

How Execution Grows With Input

As the number of nodes (n) and edges (e) grow, the code visits each node once and each edge once.

Input Size (n, e)	Approx. Operations
10 nodes, 15 edges	About 25 operations (10 for nodes + 15 for edges)
100 nodes, 200 edges	About 300 operations (100 + 200)
1000 nodes, 5000 edges	About 6000 operations (1000 + 5000)

Pattern observation: Operations grow roughly in a straight line with the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time to find shortest paths grows linearly with the number of nodes plus edges in the graph.

Common Mistake

[X] Wrong: "The algorithm checks all possible paths, so it must be exponential time."

[OK] Correct: Because the graph is a DAG and we use topological order, each edge and node is processed only once, avoiding repeated work.

Interview Connect

Understanding this time complexity helps you explain why topological order is efficient for shortest paths in DAGs, a common interview topic.

Self-Check

What if the graph had cycles? How would the time complexity and approach change?