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

Time Complexity: Dijkstra's Algorithm Single Source Shortest Path

O((n + e) log n)

Understanding Time Complexity

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

How does the number of steps change when we add more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Dijkstra's algorithm using adjacency list and priority queue
void dijkstra(int src, List> graph, int[] dist) {
    PriorityQueue pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    pq.add(new Pair(src, 0));
    while (!pq.isEmpty()) {
        Pair current = pq.poll();
        int u = current.node;
        for (Pair neighbor : graph.get(u)) {
            int v = neighbor.node;
            int w = neighbor.weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.add(new Pair(v, dist[v]));
            }
        }
    }
}
    

This code finds the shortest path from one node to all others in a weighted graph without negative edges.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs as long as there are nodes in the priority queue.
• How many times: Each edge is checked when its node is processed, so edges are examined multiple times depending on updates.
• Dominant operation: Extracting the minimum node from the priority queue and relaxing edges.

How Execution Grows With Input

As the graph grows, the number of nodes (n) and edges (e) increase, affecting how many times we process nodes and edges.

Input Size (n nodes, e edges)	Approx. Operations
10 nodes, 20 edges	About 20 edge checks and 10 node extractions
100 nodes, 500 edges	About 500 edge checks and 100 node extractions
1000 nodes, 5000 edges	About 5000 edge checks and 1000 node extractions

Pattern observation: The operations grow roughly with the number of edges and nodes, increasing linearly as the graph gets bigger.

Final Time Complexity

Time Complexity: O((n + e) log n)

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

Common Mistake

[X] Wrong: "Dijkstra's algorithm always runs in O(n²) time because it checks all nodes repeatedly."

[OK] Correct: Using a priority queue reduces repeated work, so the algorithm runs faster, especially on sparse graphs.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and why using the right data structures matters.

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 find the shortest path from a single source to all other vertices

B. To find the maximum flow in a network

C. To detect cycles in a graph

D. To sort vertices in topological order

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest distance 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 A

4. Quick Check:

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

Hint: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing with max flow algorithms
• Thinking it detects cycles
• Mixing with topological sort

2. Which Java data structure is commonly used to efficiently select the next vertex with the smallest tentative distance in Dijkstra's Algorithm?

easy

A. HashMap

B. ArrayList

C. PriorityQueue

D. LinkedList

Solution

1. Step 1: Identify the need for efficient minimum selection

   Dijkstra's Algorithm repeatedly picks the vertex with the smallest current distance. A data structure that supports quick extraction of the minimum element is needed.

2. Step 2: Match data structures to this need

   PriorityQueue in Java supports efficient retrieval of the smallest element, unlike ArrayList or LinkedList which require scanning all elements.

3. Final Answer:

   PriorityQueue -> Option C

4. Quick Check:

   PriorityQueue = efficient min extraction [OK]

Hint: Use PriorityQueue to get smallest distance vertex fast [OK]

Common Mistakes:

• Using ArrayList which is slow for min extraction
• Choosing HashMap which stores key-value pairs but not order
• Using LinkedList which is inefficient for min selection

3. What will be the output distances array after running Dijkstra's Algorithm from source vertex 0 on this graph?

int[][] graph = {
  {0, 4, 0, 0, 0, 0, 0, 8, 0},
  {4, 0, 8, 0, 0, 0, 0, 11, 0},
  {0, 8, 0, 7, 0, 4, 0, 0, 2},
  {0, 0, 7, 0, 9, 14, 0, 0, 0},
  {0, 0, 0, 9, 0, 10, 0, 0, 0},
  {0, 0, 4, 14, 10, 0, 2, 0, 0},
  {0, 0, 0, 0, 0, 2, 0, 1, 6},
  {8, 11, 0, 0, 0, 0, 1, 0, 7},
  {0, 0, 2, 0, 0, 0, 6, 7, 0}
};

medium

A. [0, 4, 12, 19, 21, 11, 9, 8, 14]

B. [0, 4, 8, 15, 20, 11, 9, 8, 10]

C. [0, 4, 7, 14, 19, 9, 8, 7, 13]

D. [0, 5, 10, 17, 22, 12, 11, 9, 15]

Solution

1. Step 1: Initialize distances and process vertices

   Start with distance 0 for vertex 0 and infinity for others. Update neighbors step-by-step using the graph edges and weights.

2. Step 2: Calculate shortest distances

   Following Dijkstra's logic, the shortest distances from vertex 0 to others are: 0 (self), 4, 12, 19, 21, 11, 9, 8, 14.

3. Final Answer:

   [0, 4, 12, 19, 21, 11, 9, 8, 14] -> Option A

4. Quick Check:

   Distances array matches [0, 4, 12, 19, 21, 11, 9, 8, 14] [OK]

Hint: Trace updates from source, pick smallest tentative distances [OK]

Common Mistakes:

• Mixing up edge weights during updates
• Not updating distances after finding shorter paths
• Confusing vertex indices

4. Identify the error in this Java snippet implementing Dijkstra's Algorithm:

for (int i = 0; i < graph.length; i++) {
  int u = pq.poll();
  for (int v = 0; v < graph.length; v++) {
    if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
      dist[v] = dist[u] + graph[u][v];
      pq.add(v);
    }
  }
}

medium

A. PriorityQueue should store distances, not vertices

B. dist array is not initialized before the loop

C. The inner loop should start from 1, not 0

D. Vertices are added to PriorityQueue without updating their priority

Solution

1. Step 1: Understand PriorityQueue usage

   The PriorityQueue must order vertices by their current shortest distance. Adding vertices without updating their priority causes incorrect ordering.

2. Step 2: Identify missing priority update

   When a shorter path is found, the vertex's priority in the queue must be updated or reinserted properly to reflect new distance.

3. Final Answer:

   Vertices are added to PriorityQueue without updating their priority -> Option D

4. Quick Check:

   PriorityQueue must reflect updated distances [OK]

Hint: Update priority in queue when distances change [OK]

Common Mistakes:

• Ignoring priority updates in PriorityQueue
• Starting loop incorrectly from 1
• Not initializing distance array

5. Given a weighted graph with some edges having zero weight, how does Dijkstra's Algorithm behave, and what modification is needed to correctly find shortest paths?

hard

A. It works normally; no modification needed

B. It may fail due to zero-weight cycles; use Bellman-Ford instead

C. It requires ignoring zero-weight edges to avoid infinite loops

D. It requires initializing distances to zero for all vertices

Solution

1. Step 1: Recall Dijkstra's requirements

   Dijkstra's Algorithm works correctly on graphs with non-negative edge weights, but zero-weight cycles can cause infinite loops or incorrect behavior.

2. Step 2: Impact of zero weights

   Zero-weight edges and zero-weight cycles may cause the algorithm to revisit vertices indefinitely. Bellman-Ford algorithm handles such cases correctly.

3. Final Answer:

   It may fail due to zero-weight cycles; use Bellman-Ford instead -> Option B

4. Quick Check:

   Bellman-Ford handles zero-weight cycles correctly [OK]

Hint: Use Bellman-Ford if zero-weight cycles exist [OK]

Common Mistakes:

• Confusing zero weights with negative weights
• Thinking zero cycles cause infinite loops
• Believing Bellman-Ford needed for zeros