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

Time Complexity: Dijkstra's Algorithm Single Source Shortest Path

O((V + E) log V)

Understanding Time Complexity

We want to understand how the time needed to find shortest paths grows as the graph gets bigger.

How does the algorithm's work increase when there are more points and connections?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function dijkstra(graph: Array>, source: number): number[] {
  const dist = Array(graph.length).fill(Infinity);
  dist[source] = 0;
  const visited = new Set();
  const pq = new MinPriorityQueue();
  pq.enqueue(source, 0);

  while (!pq.isEmpty()) {
    const { element: u } = pq.dequeue();
    if (visited.has(u)) continue;
    visited.add(u);

    for (const [v, weight] of graph[u]) {
      if (!visited.has(v) && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        pq.enqueue(v, dist[v]);
      }
    }
  }
  return dist;
}
    

This code finds the shortest distance from one starting point to all others in a weighted graph using a priority queue.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs until all nodes are visited, and inside it, the for loop checks neighbors of the current node.
• How many times: The while loop runs up to V times (number of nodes), and the for loop runs for each edge connected to the current node, totaling E edges checked.

How Execution Grows With Input

As the graph grows, the number of nodes (V) and edges (E) increase, affecting how many times the loops run.

Input Size (V, E)	Approx. Operations
10 nodes, 20 edges	About 10 dequeue operations and 20 edge relaxations
100 nodes, 500 edges	About 100 dequeue operations and 500 edge relaxations
1000 nodes, 5000 edges	About 1000 dequeue operations and 5000 edge relaxations

Pattern observation: The work grows roughly with the number of nodes plus the number of edges.

Final Time Complexity

Time Complexity: O((V + E) log V)

This means the time grows with the number of nodes and edges, multiplied by the cost of managing the priority queue.

Common Mistake

[X] Wrong: "Dijkstra's algorithm always runs in simple linear time O(V + E)."

[OK] Correct: Managing the priority queue adds a logarithmic factor, so the actual time depends on log V operations for each node or edge processed.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and why using a priority queue is important for efficiency.

Self-Check

"What if we used a simple array instead of a priority queue? How would the time complexity change?"