Dijkstra's Algorithm Single Source Shortest Path in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of Dijkstra's Algorithm?

To find the shortest path from a single starting point (source) to all other points (vertices) in a graph with non-negative edge weights.

intermediate

In Dijkstra's Algorithm, what data structure is commonly used to efficiently select the next vertex with the smallest tentative distance?

A priority queue (often implemented as a min-heap) is used to quickly pick the vertex with the smallest current distance estimate.

intermediate

Why can't Dijkstra's Algorithm handle graphs with negative edge weights?

Because it assumes that once a vertex's shortest distance is found, it won't get shorter. Negative edges can create cycles that reduce distances, breaking this assumption.

advanced

What is the time complexity of Dijkstra's Algorithm using a priority queue and adjacency list?

O((V + E) log V), where V is the number of vertices and E is the number of edges.

beginner

Explain the role of the 'distance' array in Dijkstra's Algorithm.

It stores the current shortest known distance from the source to each vertex. It updates as the algorithm finds shorter paths.

What type of graph edge weights does Dijkstra's Algorithm support?

A Only non-negative weights

B Only negative weights

C Both negative and positive weights

D No weights (unweighted graphs only)

Dijkstra's Algorithm requires non-negative edge weights to guarantee correct shortest paths.

Which data structure helps Dijkstra's Algorithm efficiently pick the next vertex to process?

A Linked List

B Queue

C Stack

D Priority Queue

A priority queue allows selecting the vertex with the smallest tentative distance efficiently.

What happens if you run Dijkstra's Algorithm on a graph with negative weight edges?

A It always finds the correct shortest paths

B It may produce incorrect results

C It runs faster

D It ignores negative edges

Negative edges can cause the algorithm to miss shorter paths, leading to wrong answers.

What does the 'distance' array represent in Dijkstra's Algorithm?

A The number of edges from source to each vertex

B The order vertices are visited

C The shortest known distance from source to each vertex

D The maximum distance found so far

The distance array keeps track of the shortest path estimates from the source.

What is the initial distance value assigned to the source vertex in Dijkstra's Algorithm?

A Zero

B Infinity

C -1

D Undefined

The source vertex distance is set to zero because the distance from the source to itself is zero.

Describe step-by-step how Dijkstra's Algorithm finds the shortest paths from a source vertex.

Think about how the algorithm explores vertices and updates distances.

Explain why Dijkstra's Algorithm cannot handle negative edge weights and what could happen if it tries.

Consider how negative weights affect the distance updates.

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