Dijkstra's algorithm in Data Structures Theory - Time & Space Complexity

Time Complexity: Dijkstra's algorithm

O(n^2)

Understanding Time Complexity

Dijkstra's algorithm finds the shortest path from one point to all others in a network.

We want to know how the time it takes grows as the network gets bigger.

Scenario Under Consideration

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

function dijkstra(graph, start):
  dist = map with all nodes set to infinity
  dist[start] = 0
  visited = empty set
  while there are unvisited nodes:
    current = node with smallest dist not visited
    mark current as visited
    for each neighbor of current:
      if dist[current] + edge_weight < dist[neighbor]:
        dist[neighbor] = dist[current] + edge_weight
  return dist
    

This code finds shortest distances from the start node to all others by updating distances step-by-step.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Selecting the unvisited node with the smallest distance and updating neighbors.
• How many times: This happens once for each node, so about n times where n is number of nodes.

How Execution Grows With Input

As the number of nodes and edges grows, the work to find the closest node and update neighbors grows too.

Input Size (n nodes)	Approx. Operations
10	About 100 to 200 operations
100	About 10,000 to 20,000 operations
1000	About 1,000,000 to 2,000,000 operations

Pattern observation: The operations grow roughly with the square of the number of nodes because each node's neighbors are checked multiple times.

Final Time Complexity

Time Complexity: O(n^2)

This means if you double the number of nodes, the time to run the algorithm roughly quadruples.

Common Mistake

[X] Wrong: "Dijkstra's algorithm always runs very fast regardless of graph size because it just picks the shortest path step-by-step."

[OK] Correct: The algorithm must check many nodes and edges, so as the graph grows, the work grows quickly, especially if implemented without efficient data structures.

Interview Connect

Understanding how Dijkstra's algorithm scales helps you explain your choices and shows you grasp how algorithms behave on bigger problems.

Self-Check

"What if we use a priority queue (min-heap) to select the smallest distance node? How would the time complexity change?"

Practice

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

easy

A. To detect cycles in a graph

B. To sort nodes in alphabetical order

C. To find the maximum flow in a network

D. To find the shortest path from one node to all other nodes in a weighted graph

Solution

1. Step 1: Understand the goal of Dijkstra's algorithm

   Dijkstra's algorithm is designed to find the shortest distances from a starting node to all other nodes in a graph where edges have weights.

2. Step 2: Compare with other graph algorithms

   Sorting nodes or detecting cycles are different tasks handled by other algorithms, not Dijkstra's.

3. Final Answer:

   To find the shortest path from one node to all other nodes in a weighted graph -> Option D

4. Quick Check:

   Shortest path finding = To find the shortest path from one node to all other nodes in a weighted graph [OK]

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

Common Mistakes:

• Confusing shortest path with sorting or cycle detection
• Thinking it finds maximum flow
• Assuming it works on unweighted graphs only

2. Which of the following is the correct step in Dijkstra's algorithm?

easy

A. Select the unvisited node with the smallest tentative distance

B. Select the visited node with the largest distance

C. Update distances by adding the maximum edge weight

D. Remove nodes with the highest degree first

Solution

1. Step 1: Identify the selection criteria in Dijkstra's algorithm

   The algorithm always picks the unvisited node with the smallest tentative distance to explore next.

2. Step 2: Eliminate incorrect options

   Choosing visited nodes or using maximum edge weights contradicts the algorithm's logic.

3. Final Answer:

   Select the unvisited node with the smallest tentative distance -> Option A

4. Quick Check:

   Pick closest unvisited node = Select the unvisited node with the smallest tentative distance [OK]

Hint: Always pick closest unvisited node next [OK]

Common Mistakes:

• Picking visited nodes again
• Adding maximum instead of minimum edge weights
• Removing nodes based on degree

3. Consider the graph with nodes A, B, C and edges: A-B (4), A-C (2), C-B (1). Starting from A, what is the shortest distance to B using Dijkstra's algorithm?

medium

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Initialize distances from A

   Distance to A is 0, to B is infinity, to C is infinity initially.

2. Step 2: Update distances via neighbors

   From A, distance to C is 2, to B is 4. Next, from C, distance to B is 2 + 1 = 3, which is less than 4, so update B's distance to 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Shortest path A->C->B = 3 [OK]

Hint: Check all paths, pick minimum sum of edges [OK]

Common Mistakes:

• Ignoring the path through C
• Choosing direct edge without comparison
• Mixing up edge weights

4. In the following pseudocode for Dijkstra's algorithm, what is the error?

1. Initialize distances to infinity
2. Set distance to start node as 0
3. While unvisited nodes remain:
4.    Pick any unvisited node
5.    Update distances to neighbors
6.    Mark node as visited

medium

A. Not initializing distances to zero

B. Picking any unvisited node instead of the one with smallest distance

C. Marking nodes as visited before updating distances

D. Setting start node distance to infinity

Solution

1. Step 1: Identify the node selection step

   The algorithm must pick the unvisited node with the smallest tentative distance, not just any node.

2. Step 2: Understand the impact of wrong selection

   Picking any node can lead to incorrect shortest paths because it ignores the priority of closer nodes.

3. Final Answer:

   Picking any unvisited node instead of the one with smallest distance -> Option B

4. Quick Check:

   Must pick closest unvisited node [OK]

Hint: Always pick node with smallest tentative distance [OK]

Common Mistakes:

• Choosing nodes randomly
• Setting wrong initial distances
• Marking nodes visited too early

5. You have a weighted graph with some edges having zero weight. How does Dijkstra's algorithm handle zero-weight edges when finding shortest paths?

hard

A. It treats zero-weight edges as infinite weight edges

B. It ignores zero-weight edges completely

C. It treats zero-weight edges like any other edge and updates distances accordingly

D. It causes the algorithm to fail or loop infinitely

Solution

1. Step 1: Understand edge weights in Dijkstra's algorithm

   Dijkstra's algorithm works with non-negative weights, including zero, treating them as valid edges.

2. Step 2: Effect of zero-weight edges

   Zero-weight edges allow the algorithm to update distances without adding cost, effectively moving to connected nodes at no extra distance.

3. Final Answer:

   It treats zero-weight edges like any other edge and updates distances accordingly -> Option C

4. Quick Check:

   Zero weight edges are valid and processed [OK]

Hint: Zero weight edges count as normal edges with no added cost [OK]

Common Mistakes:

• Ignoring zero-weight edges thinking they cause errors
• Assuming zero weight means infinite cost
• Believing algorithm loops infinitely with zero weights