Dijkstra's Algorithm Single Source Shortest Path in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dijkstra's Algorithm on a Simple Graph

What is the shortest distance array output after running Dijkstra's algorithm from source node 0 on the given graph?

DSA Java

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}
};
int source = 0;
int[] dist = dijkstra(graph, source);
System.out.println(Arrays.toString(dist));

A [0, 4, 8, 15, 20, 11, 9, 8, 14]

B [0, 4, 12, 21, 23, 11, 9, 8, 14]

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

D [0, 4, 8, 19, 21, 11, 9, 8, 14]

💡 Hint

Trace the shortest paths step-by-step from the source node 0.

Dijkstra's algorithm finds the shortest path from source 0 to all other nodes. The distances array shows the minimum distances after processing all nodes.

🧠 Conceptual

intermediate

Understanding Priority Queue Role in Dijkstra's Algorithm

What is the main purpose of using a priority queue in Dijkstra's algorithm?

A To always pick the next node with the smallest tentative distance to process

B To store all nodes in alphabetical order

C To reverse the order of nodes before processing

D To keep track of visited nodes only

💡 Hint

Think about how the algorithm decides which node to explore next.

The priority queue helps pick the node with the smallest current distance, ensuring the shortest paths are found efficiently.

🔧 Debug

advanced

Identify the Error in Dijkstra's Algorithm Implementation

Given the following snippet from a Dijkstra's algorithm implementation, what error will occur when running it?

DSA Java

int[] dist = new int[V];
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
  dist[i] = Integer.MAX_VALUE;
}
dist[source] = 0;

for (int count = 0; count < V - 1; count++) {
  int u = minDistance(dist, visited);
  visited[u] = true;

  for (int v = 0; v < V; v++) {
    if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
      dist[v] = dist[u] + graph[u][v];
    }
  }
}

// Missing minDistance method implementation

A Compilation error due to missing minDistance method

B Runtime NullPointerException when accessing dist array

C ArrayIndexOutOfBoundsException when accessing graph

D Infinite loop because visited array is never updated

💡 Hint

Check if all methods used are defined.

The code calls minDistance but does not define it, causing a compilation error.

🚀 Application

advanced

Applying Dijkstra's Algorithm to Find Shortest Path

Given the weighted graph below, what is the shortest path distance from node 2 to node 6?

Graph edges with weights: (2-3:7), (2-5:4), (3-4:9), (5-6:2), (6-7:1)

A 11

B 7

C 9

D 6

💡 Hint

Consider direct and indirect paths and sum weights.

The shortest path from 2 to 6 is 2->5->6 with total weight 6.

🧠 Conceptual

expert

Why Dijkstra's Algorithm Fails with Negative Weights

Why does Dijkstra's algorithm not work correctly if the graph contains edges with negative weights?

A Because it cannot handle graphs with cycles

B Because it assumes once a node's shortest distance is found, it cannot be improved later

C Because it uses a priority queue which does not support negative numbers

D Because it only works on directed graphs

💡 Hint

Think about the algorithm's assumption about distances once visited.

Dijkstra's algorithm assumes that once a node is processed, its shortest distance is final. Negative edges can later reduce that distance, breaking this assumption.

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