Dijkstra's Algorithm Single Source Shortest Path in DSA C++ - 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 by Dijkstra's algorithm grows as the graph size increases.

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.

#include <vector>
#include <queue>
#include <utility>
using namespace std;

void dijkstra(int start, const vector<vector<pair<int,int>>>& graph, vector<int>& dist) {
  dist[start] = 0;
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
  pq.push({0, start});

  while (!pq.empty()) {
    int d = pq.top().first;
    int u = pq.top().second;
    pq.pop();
    if (d > dist[u]) continue;
    for (auto &edge : graph[u]) {
      int v = edge.first, w = edge.second;
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push({dist[v], v});
      }
    }
  }
}
    

This code finds the shortest path distances from a start node to all others in a weighted graph using a priority queue.

Identify Repeating Operations

Look for loops and repeated steps that take most time.

• Primary operation: The while loop runs as long as there are nodes in the priority queue.
• How many times: Each edge is checked at most once when relaxing distances, so up to E times, where E is number of edges.
• The priority queue push/pop operations happen up to O(E) times.

How Execution Grows With Input

As the graph grows, the number of nodes V and edges E increase, affecting operations.

Input Size (V, E)	Approx. Operations
V=10, E=20	About 20 priority queue operations and edge relaxations
V=100, E=500	About 500 priority queue operations and edge relaxations
V=1000, E=5000	About 5000 priority queue operations and edge relaxations

Pattern observation: The work grows roughly proportional to the number of edges and nodes combined.

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 priority queue operations.

Common Mistake

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

[OK] Correct: The priority queue operations take extra time, adding a logarithmic factor, so it is not just linear.

Interview Connect

Understanding this time complexity helps you explain how efficient your shortest path solution is and why priority queues matter.

Self-Check

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

Practice

1. What is the main purpose of Dijkstra's Algorithm in graph theory?

easy

A. To sort vertices in topological order

B. To find the maximum flow in a network

C. To detect cycles in a graph

D. To find the shortest path from a single source to all other vertices

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest distances from one starting point (source) to every other point in a graph with non-negative edge weights.

2. Step 2: Compare with other graph algorithms

   Other algorithms like max flow or cycle detection serve different purposes, so they do not match Dijkstra's goal.

3. Final Answer:

   To find the shortest path from a single source to all other vertices -> Option D

4. Quick Check:

   Dijkstra's Algorithm = shortest paths from source [OK]

Hint: Remember: Dijkstra finds shortest paths from one source [OK]

Common Mistakes:

• Confusing Dijkstra with algorithms for max flow
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which of the following is the correct way to initialize the distance array in Dijkstra's Algorithm in C++?

easy

A. vector<int> dist(n, -1); dist[source] = 0;

B. vector<int> dist(n, INT_MAX); dist[source] = 0;

C. vector<int> dist(n, 0); dist[source] = INT_MAX;

D. vector<int> dist(n); dist[source] = 0;

Solution

1. Step 1: Understand distance initialization

   Distances to all nodes except the source should start as infinity (or a very large number) to represent unknown distance.

2. Step 2: Check each option

   vector<int> dist(n, INT_MAX); dist[source] = 0; correctly sets all distances to INT_MAX and source distance to 0. Others either set wrong initial values or leave uninitialized.

3. Final Answer:

   vector<int> dist(n, INT_MAX); dist[source] = 0; -> Option B

4. Quick Check:

   Distance array initialized with INT_MAX except source = 0 [OK]

Hint: Initialize all distances to max except source zero [OK]

Common Mistakes:

• Setting all distances to zero initially
• Not setting source distance to zero
• Leaving distance array uninitialized

3. Consider the following graph edges and weights:

0 -> 1 (4), 0 -> 2 (1), 2 -> 1 (2), 1 -> 3 (1), 2 -> 3 (5)

If we run Dijkstra's Algorithm from source vertex 0, what is the shortest distance array after completion?

medium

A. [0, 3, 1, 4]

B. [0, 4, 1, 6]

C. [0, 2, 1, 3]

D. [0, 5, 1, 7]

Solution

1. Step 1: Initialize distances

   Start with dist = [0, INF, INF, INF]. Source 0 distance is 0.

2. Step 2: Relax edges step-by-step

   From 0: dist[1] = 4, dist[2] = 1. From 2: dist[1] = min(4, 1+2=3) = 3, dist[3] = 1+5=6. From 1: dist[3] = min(6, 3+1=4) = 4.

3. Final Answer:

   [0, 3, 1, 4] -> Option A

4. Quick Check:

   Shortest distances from 0 = [0,3,1,4] [OK]

Hint: Update distances by relaxing edges with minimum sums [OK]

Common Mistakes:

• Not updating distance to vertex 1 via vertex 2
• Incorrectly summing edge weights
• Ignoring better paths found later

4. The following C++ code snippet for Dijkstra's Algorithm has a bug. What is the error?

vector<int> dist(n, INT_MAX);
dist[source] = 0;
priority_queue> pq;
pq.push({0, source});
while(!pq.empty()) {
  int u = pq.top().second;
  int d = pq.top().first;
  pq.pop();
  if(d > dist[u]) continue;
  for(auto &edge : graph[u]) {
    int v = edge.first;
    int w = edge.second;
    if(dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
      pq.push({dist[v], v});
    }
  }
}

medium

A. priority_queue is max-heap by default (needs negative distances or greater comparator)

B. Distance array is not initialized correctly

C. The graph adjacency list is not iterated properly

D. The source distance is not set to zero

Solution

1. Step 1: Check priority queue usage

   In C++, priority_queue by default is max-heap. To get min-heap behavior for distances, distances should be pushed as negative or use greater comparator.

2. Step 2: Identify the bug

   The code pushes distances as positive values, so the smallest distance won't be on top, causing incorrect behavior.

3. Final Answer:

   priority_queue is max-heap by default (needs negative distances or greater comparator) -> Option A

4. Quick Check:

   Use negative distances or min-heap for correct priority queue [OK]

Hint: Use negative distances or min-heap to get smallest distance first [OK]

Common Mistakes:

• Ignoring priority queue ordering behavior
• Not setting source distance to zero
• Incorrect graph iteration

5. You have a weighted graph with 5 vertices and edges:

0->1(10), 0->4(5), 1->2(1), 2->3(4), 4->1(3), 4->2(9), 4->3(2), 3->0(7)

Using Dijkstra's Algorithm from source 0, what is the shortest distance to vertex 3?

hard

A. 13

B. 15

C. 7

D. 18

Solution

1. Step 1: Initialize distances

   dist = [0, INF, INF, INF, INF]. Source 0 distance is 0.

2. Step 2: Relax edges step-by-step

   From 0: dist[1]=10, dist[4]=5. From 4: dist[1]=min(10,5+3=8)=8, dist[2]=min(INF,5+9=14)=14, dist[3]=min(INF,5+2=7)=7. From 1: dist[2]=min(14,8+1=9)=9. From 2: dist[3]=min(7,9+4=13)=7.

3. Step 3: Final shortest distance to vertex 3

   The shortest distance to vertex 3 is 7.

4. Final Answer:

   7 -> Option C

5. Quick Check:

   Shortest distance to vertex 3 = 7 [OK]

Hint: Relax edges in order, update distances with minimum sums [OK]

Common Mistakes:

• Not updating distances via vertex 4
• Ignoring better paths through intermediate vertices
• Confusing edge weights