Dijkstra's Algorithm Single Source Shortest Path in DSA Java - Build from Scratch

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: You are working as a city planner. You have a map of intersections connected by roads with distances. You want to find the shortest distance from a starting intersection to all other intersections.

🎯 Goal: Build a Java program that uses Dijkstra's algorithm to find the shortest path distances from a given start intersection to all other intersections in the city map.

📋 What You'll Learn

Create a graph using an adjacency matrix with exact distances

Use a variable to track the number of intersections

Implement Dijkstra's algorithm to find shortest distances

Print the shortest distances from the start intersection to all others

💡 Why This Matters

🌍 Real World

City planners and GPS systems use shortest path algorithms like Dijkstra's to find the quickest routes between locations.

💼 Career

Understanding Dijkstra's algorithm is essential for software engineers working on navigation, mapping, and network routing applications.

1

Create the graph as an adjacency matrix

Create a 2D integer array called graph with 4 intersections and these exact distances:
From intersection 0 to 1 is 5, to 2 is 10, to 3 is 0 (no direct road).
From 1 to 0 is 5, to 2 is 3, to 3 is 1.
From 2 to 0 is 10, to 1 is 3, to 3 is 7.
From 3 to 0 is 0, to 1 is 1, to 2 is 7.
Use 0 to represent no direct road between intersections.

DSA Java

# Create the adjacency matrix graph with exact distances
# Your code here

Hint

Use a 2D array with 4 rows and 4 columns. Each row represents an intersection and each column the distance to another intersection.

2

Add a variable for the number of intersections

Create an integer variable called V and set it to the number of intersections in the graph (4).

DSA Java

int[][] graph = {
    {0, 5, 10, 0},
    {5, 0, 3, 1},
    {10, 3, 0, 7},
    {0, 1, 7, 0}
};
// Create variable V for number of intersections
// Your code here

Hint

Count the rows or columns in the graph to find the number of intersections.

3

Implement Dijkstra's algorithm to find shortest distances

Write a method called dijkstra that takes graph, V, and a start intersection src as parameters. Use arrays dist to store shortest distances and visited to track visited intersections. Initialize dist[src] to 0 and others to a large number (e.g., 10000). Use a loop to find the unvisited intersection with the smallest distance, mark it visited, and update distances to neighbors if shorter paths are found.

DSA Java

int[][] graph = {
    {0, 5, 10, 0},
    {5, 0, 3, 1},
    {10, 3, 0, 7},
    {0, 1, 7, 0}
};
int V = 4;

// Write dijkstra method below
// Your code here

Hint

Use two arrays: one for distances and one for visited intersections. Update distances only if a shorter path is found.

4

Call the method and print shortest distances

Call the dijkstra method with graph, V, and start intersection 0. This will print the shortest distances from intersection 0 to all others.

DSA Java

int[][] graph = {
    {0, 5, 10, 0},
    {5, 0, 3, 1},
    {10, 3, 0, 7},
    {0, 1, 7, 0}
};
int V = 4;

public static void dijkstra(int[][] graph, int V, int src) {
    // method code here
}

// Call dijkstra with start intersection 0
// Your code here

Hint

Call the dijkstra method inside the main method with start intersection 0.

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