Dijkstra's Algorithm Single Source Shortest Path in DSA Java - Execution Trace

Concept Flow - Dijkstra's Algorithm Single Source Shortest Path

Start: Initialize distances

↓

Set source distance = 0

↓

While unvisited nodes remain

↓

Pick unvisited node with smallest distance

↓

For each neighbor

↓

Calculate new distance

↓

If new distance < known distance

↓

Update distance and predecessor

↓

Mark current node visited

↓

Repeat until all nodes visited

↓

Shortest paths found

Dijkstra's algorithm finds shortest paths from one node to all others by repeatedly picking the closest unvisited node and updating distances.

Execution Sample

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[src] = 0;
for (int count = 0; count < V - 1; count++) {
  int u = minDistance(dist, visited); // pick closest unvisited
  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];
    }
  }
}

This code finds shortest distances from source to all nodes in a weighted graph using Dijkstra's algorithm.

Execution Table

Step	Operation	Current Node (u)	Distances Array	Visited Set	Visual State
1	Initialize distances	N/A	[0, ∞, ∞, ∞, ∞]	{}	Start with source node 0 distance 0, others infinity
2	Pick node with min distance	0	[0, ∞, ∞, ∞, ∞]	{}	Select node 0 as current
3	Update neighbors of 0	0	[0, 10, 3, ∞, ∞]	{}	Update distances to neighbors: node1=10, node2=3
4	Mark node 0 visited	0	[0, 10, 3, ∞, ∞]	{0}	Node 0 added to visited
5	Pick node with min distance	2	[0, 10, 3, ∞, ∞]	{0}	Select node 2 (distance 3)
6	Update neighbors of 2	2	[0, 10, 3, 6, ∞]	{0}	Update node3 distance to 6 via node2
7	Mark node 2 visited	2	[0, 10, 3, 6, ∞]	{0,2}	Node 2 added to visited
8	Pick node with min distance	3	[0, 10, 3, 6, ∞]	{0,2}	Select node 3 (distance 6)
9	Update neighbors of 3	3	[0, 10, 3, 6, 9]	{0,2}	Update node4 distance to 9 via node3
10	Mark node 3 visited	3	[0, 10, 3, 6, 9]	{0,2,3}	Node 3 added to visited
11	Pick node with min distance	1	[0, 10, 3, 6, 9]	{0,2,3}	Select node 1 (distance 10)
12	Update neighbors of 1	1	[0, 10, 3, 6, 9]	{0,2,3}	No shorter paths found
13	Mark node 1 visited	1	[0, 10, 3, 6, 9]	{0,1,2,3}	Node 1 added to visited
14	Pick node with min distance	4	[0, 10, 3, 6, 9]	{0,1,2,3}	Select node 4 (distance 9)
15	Update neighbors of 4	4	[0, 10, 3, 6, 9]	{0,1,2,3}	No neighbors to update
16	Mark node 4 visited	4	[0, 10, 3, 6, 9]	{0,1,2,3,4}	Node 4 added to visited
17	All nodes visited	N/A	[0, 10, 3, 6, 9]	{0,1,2,3,4}	Algorithm ends, shortest distances found

💡 All nodes visited, shortest distances finalized

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	After Step 15	Final
dist	[0, ∞, ∞, ∞, ∞]	[0, 10, 3, ∞, ∞]	[0, 10, 3, 6, ∞]	[0, 10, 3, 6, 9]	[0, 10, 3, 6, 9]	[0, 10, 3, 6, 9]	[0, 10, 3, 6, 9]
visited	{}	{}	{0,2}	{0,2,3}	{0,1,2,3}	{0,1,2,3,4}	{0,1,2,3,4}
current node (u)	N/A	0	2	3	1	4	N/A

Key Moments - 3 Insights

Why do we pick the unvisited node with the smallest distance each time?

Because picking the closest unvisited node ensures we find the shortest path step-by-step, as shown in execution_table rows 2, 5, 8, 11, and 14 where the current node is chosen by minimum distance.

Why do distances update only if the new path is shorter?

Distances update only when the new calculated distance is less than the current known distance, ensuring we keep the shortest path. This is seen in rows 3, 6, and 9 where distances improve.

What happens when a node is marked visited?

Once a node is visited (rows 4, 7, 10, 13, 16), it means its shortest distance is finalized and won't be updated again, preventing cycles and repeated work.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the distance to node 3?

A ∞

B 6

C 3

D 10

💡 Hint

Check the Distances Array column at step 6 in the execution_table.

At which step does node 1 get marked as visited?

A Step 13

B Step 14

C Step 10

D Step 7

💡 Hint

Look at the Visited Set column in execution_table rows to find when node 1 is added.

If the edge from node 2 to node 3 had weight 10 instead of 3, how would the distance to node 3 change after step 6?

A It would remain ∞

B It would be 10

C It would be 13

D It would be 6

💡 Hint

Consider how distances update in execution_table step 6 and the formula dist[u] + graph[u][v].

Concept Snapshot

Dijkstra's Algorithm:
- Initialize all distances to infinity except source = 0
- Pick unvisited node with smallest distance
- Update neighbors' distances if shorter path found
- Mark node visited after processing
- Repeat until all nodes visited
- Result: shortest distances from source to all nodes

Full Transcript

Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a weighted graph. It starts by setting the distance to the source as zero and all others as infinity. Then, it repeatedly selects the unvisited node with the smallest known distance, updates the distances of its neighbors if a shorter path is found through it, and marks it as visited. This process continues until all nodes are visited, ensuring the shortest paths are found. The execution table shows each step, the current node chosen, the distances array updates, and the visited nodes. Key moments clarify why the closest node is chosen, why distances update only if shorter, and what marking visited means. The visual quiz tests understanding of distances at specific steps, when nodes are visited, and how edge weight changes affect distances.

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