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

Time Complexity: Shortest Path in DAG Using Topological Order

O(V + E)

Understanding Time Complexity

We want to know how fast we can find the shortest path in a Directed Acyclic Graph (DAG) using topological order.

How does the time needed grow as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void shortestPath(int src, int V, vector> adj[]) {
    vector dist(V, INT_MAX);
    dist[src] = 0;
    stack st;
    vector visited(V, false);

    // Topological sort helper
    for (int i = 0; i < V; i++) {
        if (!visited[i]) dfs(i, adj, visited, st);
    }

    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (dist[u] != INT_MAX) {
            for (auto &edge : adj[u]) {
                int v = edge.first, w = edge.second;
                if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
            }
        }
    }
}

This code finds shortest paths from a source node in a DAG by first ordering nodes topologically, then relaxing edges in that order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DFS calls for topological sort and edge relaxation loops.
• How many times: DFS visits each node and edge once; edge relaxation loops run once per node's outgoing edges.

How Execution Grows With Input

As the number of nodes (V) and edges (E) grow, the work grows roughly with the sum of nodes and edges.

Input Size (V, 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: The total work grows linearly with the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(V + E)

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

Common Mistake

[X] Wrong: "The algorithm takes O(V * E) time because it checks all edges for each node repeatedly."

[OK] Correct: Each edge and node is processed only once due to topological order and DFS, so the work adds up, not multiplies.

Interview Connect

Understanding this linear time approach shows you can efficiently solve shortest path problems in DAGs, a key skill for many graph challenges.

Self-Check

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