Dijkstra's Algorithm Single Source Shortest Path in DSA C - Time & Space Complexity

Time Complexity: Dijkstra's Algorithm Single Source Shortest Path

O(V^2)

Understanding Time Complexity

We want to understand how the time needed by Dijkstra's algorithm changes as the graph size grows.

Specifically, how the number of nodes and edges affects the work done to find shortest paths.

Scenario Under Consideration

Analyze the time complexity of the following Dijkstra's algorithm code snippet.

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    dist[src] = 0;
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] > 0 && dist[u] != INT_MAX 
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}
    

This code finds shortest paths from one node to all others using a simple array and adjacency matrix.

Identify Repeating Operations

Look at the loops and repeated steps:

• Primary operation: The outer loop runs once for each node (V times).
• Nested operation: Inside, it finds the minimum distance node (scans all V nodes).
• Inner loop: For each chosen node, it checks all neighbors (V nodes) to update distances.
• Dominant work: The nested loops scanning all nodes make the main cost.

How Execution Grows With Input

As the number of nodes (V) grows, the work grows roughly with the square of V.

Input Size (V)	Approx. Operations
10	About 100 (10 x 10) checks
100	About 10,000 (100 x 100) checks
1000	About 1,000,000 (1000 x 1000) checks

Pattern observation: Doubling nodes roughly quadruples the work because of nested loops.

Final Time Complexity

Time Complexity: O(V2)

This means the time needed grows roughly with the square of the number of nodes in the graph.

Common Mistake

[X] Wrong: "Dijkstra's algorithm always runs in linear time because it just visits each node once."

[OK] Correct: The algorithm repeatedly scans all nodes to find the closest unvisited node and updates neighbors, causing nested loops that increase time with the square of nodes.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and why using better data structures can improve performance.

Self-Check

"What if we replace the array with a priority queue (min-heap) to find the minimum distance node? How would the time complexity change?"