Dijkstra's Algorithm Single Source Shortest Path in DSA Java - Deep Dive

Overview - Dijkstra's Algorithm Single Source Shortest Path

What is it?

Dijkstra's Algorithm finds the shortest path from one starting point to all other points in a network or map. It works by exploring paths step-by-step, always choosing the closest unvisited point next. This helps find the quickest way to reach every destination from the start. It is widely used in navigation and network routing.

Why it matters

Without Dijkstra's Algorithm, finding the shortest routes in maps or networks would be slow and inefficient, especially as the size grows. It solves the problem of quickly knowing the best path to travel, saving time and resources. This impacts GPS navigation, internet data routing, and many real-world systems that depend on fast, optimal paths.

Where it fits

Before learning Dijkstra's Algorithm, you should understand graphs, nodes, edges, and basic data structures like priority queues. After mastering it, you can explore more advanced shortest path algorithms like A* or Bellman-Ford, and graph optimization techniques.

Mental Model

Core Idea

Always pick the closest unvisited point and update the shortest known paths until all points are reached.

Think of it like...

Imagine you are delivering packages in a city. You start at your warehouse and always go next to the closest house you haven't delivered to yet, updating your best route as you go.

Start (S)
  |
  v
[Visited Nodes] <-- Keep track of shortest distances
  |
  v
[Priority Queue] <-- Always pick the closest unvisited node
  |
  v
[Update distances to neighbors]
  |
  v
Repeat until all nodes visited

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Paths

Concept: Introduce graphs as points connected by lines and the idea of paths between points.

A graph is a collection of points called nodes connected by lines called edges. Each edge can have a cost or distance. A path is a sequence of edges connecting two nodes. For example, in a city map, intersections are nodes and roads are edges with distances.

Result

You can visualize a network of points and understand that traveling from one point to another involves following edges.

Understanding graphs and paths is essential because shortest path algorithms work by exploring these connections.

2

Foundation

What is Shortest Path Problem?

Concept: Define the problem of finding the minimum cost path from one node to another in a graph.

The shortest path problem asks: what is the least costly way to get from a starting node to a target node? Cost can be distance, time, or any measure. For example, finding the quickest route from home to school on a map.

Result

You know the goal is to find the path with the smallest total cost between two points.

Knowing the problem clearly helps focus on how algorithms like Dijkstra solve it efficiently.

3

Intermediate

Dijkstra's Algorithm Basic Steps

🤔Before reading on: do you think Dijkstra's algorithm updates all nodes at once or one by one? Commit to your answer.

Concept: Introduce the step-by-step process of picking the closest unvisited node and updating distances.

Start with the source node, set its distance to zero, and all others to infinity. Use a priority queue to pick the closest unvisited node. For each neighbor, update its distance if a shorter path is found through the current node. Mark the current node as visited and repeat until all nodes are visited.

Result

You get the shortest distance from the source to every other node in the graph.

Understanding the greedy choice of always picking the closest node ensures the algorithm finds the shortest paths correctly.

4

Intermediate

Implementing with Priority Queue

🤔Before reading on: do you think a simple list or a priority queue is better for picking the next node? Commit to your answer.

Concept: Explain why a priority queue is used to efficiently select the next closest node.

A priority queue keeps nodes sorted by their current shortest distance. This lets the algorithm quickly pick the closest unvisited node without scanning all nodes. In Java, a PriorityQueue class can be used to store nodes with their distances.

Result

The algorithm runs faster, especially on large graphs, because it avoids unnecessary checks.

Knowing the role of the priority queue helps understand the algorithm's efficiency and why it scales well.

5

Intermediate

Handling Graphs with Weighted Edges

🤔Before reading on: do you think Dijkstra's algorithm works with negative edge weights? Commit to your answer.

Concept: Clarify that Dijkstra's algorithm requires non-negative edge weights and explain why.

Dijkstra's algorithm assumes all edge weights are zero or positive. Negative weights can cause the algorithm to pick wrong paths because it always trusts the current shortest distance. For graphs with negative edges, other algorithms like Bellman-Ford are used.

Result

You understand the limitation and know when not to use Dijkstra's algorithm.

Recognizing this constraint prevents applying the algorithm incorrectly and ensures correct results.

6

Advanced

Java Code Example with Comments

🤔Before reading on: predict what the output distances will be for a simple graph with nodes A, B, C and edges A-B=4, A-C=2, C-B=1. Commit to your answer.

Concept: Show a complete Java implementation of Dijkstra's algorithm with clear comments.

import java.util.*; class Node implements Comparable { int vertex; int distance; Node(int vertex, int distance) { this.vertex = vertex; this.distance = distance; } public int compareTo(Node other) { return Integer.compare(this.distance, other.distance); } } public class Dijkstra { public static int[] dijkstra(int vertices, List> graph, int start) { int[] dist = new int[vertices]; Arrays.fill(dist, Integer.MAX_VALUE); dist[start] = 0; PriorityQueue pq = new PriorityQueue<>(); pq.add(new Node(start, 0)); boolean[] visited = new boolean[vertices]; while (!pq.isEmpty()) { Node current = pq.poll(); int u = current.vertex; if (visited[u]) continue; visited[u] = true; for (Node neighbor : graph.get(u)) { int v = neighbor.vertex; int weight = neighbor.distance; if (!visited[v] && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.add(new Node(v, dist[v])); } } } return dist; } public static void main(String[] args) { int vertices = 3; List> graph = new ArrayList<>(); for (int i = 0; i < vertices; i++) { graph.add(new ArrayList<>()); } // Edges: A(0)-B(1)=4, A(0)-C(2)=2, C(2)-B(1)=1 graph.get(0).add(new Node(1, 4)); graph.get(0).add(new Node(2, 2)); graph.get(2).add(new Node(1, 1)); int[] distances = dijkstra(vertices, graph, 0); for (int i = 0; i < distances.length; i++) { System.out.println("Distance from A to " + (char)('A' + i) + " is " + distances[i]); } } }

Result

Distance from A to A is 0 Distance from A to B is 3 Distance from A to C is 2

Seeing the full code with comments connects theory to practice and clarifies how each part works together.

7

Expert

Algorithm Optimization and Variants

🤔Before reading on: do you think Dijkstra's algorithm can be improved for very large graphs? Commit to your answer.

Concept: Discuss optimizations like using Fibonacci heaps and variants like bidirectional Dijkstra.

For very large graphs, using a Fibonacci heap instead of a binary heap can reduce the time complexity of decrease-key operations, speeding up the algorithm. Bidirectional Dijkstra runs two simultaneous searches from start and end nodes, meeting in the middle to reduce search space. These optimizations improve performance in real-world applications like GPS and network routing.

Result

You learn how to make Dijkstra's algorithm faster and more scalable for big problems.

Knowing these advanced optimizations helps when working with large-scale systems where performance is critical.

Under the Hood

Dijkstra's algorithm maintains a set of nodes with known shortest distances from the start. It uses a priority queue to always pick the node with the smallest tentative distance. When a node is picked, its neighbors are checked and their distances updated if a shorter path is found through the current node. This process repeats until all nodes are visited, ensuring the shortest paths are found by gradually expanding the frontier of known shortest distances.

Why designed this way?

The algorithm was designed by Edsger Dijkstra in 1956 to efficiently solve shortest path problems without exploring all paths exhaustively. The greedy approach of always picking the closest node ensures correctness and efficiency. Alternatives like Bellman-Ford handle negative edges but are slower. The priority queue structure was chosen to optimize selection of the next node to process.

┌───────────────┐
│ Start Node (S)│
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Priority Queue│
│ (nodes by    │
│  shortest dist)│
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Pick closest  │
│ unvisited node│
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Update neighbors│
│ distances if   │
│ shorter path   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Mark node as  │
│ visited       │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Repeat until  │
│ all visited   │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does Dijkstra's algorithm work correctly with negative edge weights? Commit to yes or no.

Common Belief: Dijkstra's algorithm can handle negative edge weights just fine.

Reality: Dijkstra's algorithm does not work correctly with negative edge weights because it assumes once a node's shortest distance is found, it cannot be improved.

Why it matters: Using Dijkstra on graphs with negative edges can produce wrong shortest paths, leading to incorrect routing or decisions.

Quick: Does Dijkstra's algorithm always find the shortest path to all nodes even if some nodes are unreachable? Commit to yes or no.

Common Belief: Dijkstra's algorithm always finds shortest paths to all nodes in the graph.

Reality: Dijkstra's algorithm only finds shortest paths to nodes reachable from the start; unreachable nodes remain at infinite distance.

Why it matters: Assuming all nodes are reachable can cause errors in applications expecting valid paths everywhere.

Quick: Is a simple list enough to pick the next node efficiently in Dijkstra's algorithm? Commit to yes or no.

Common Belief: Using a simple list to pick the next node is efficient enough for Dijkstra's algorithm.

Reality: Using a simple list leads to slower performance because it requires scanning all nodes to find the closest unvisited node.

Why it matters: Ignoring efficient data structures like priority queues can make the algorithm impractical for large graphs.

Expert Zone

1

Dijkstra's algorithm can be adapted to find shortest paths in graphs with special constraints by modifying edge weights or the priority queue logic.

2

The choice of data structure for the priority queue (binary heap vs Fibonacci heap) affects performance trade-offs between insertion and decrease-key operations.

3

In dense graphs, using adjacency matrices with Dijkstra can be simpler but less efficient than adjacency lists with priority queues.

When NOT to use

Do not use Dijkstra's algorithm if the graph has negative edge weights; use Bellman-Ford instead. For heuristic-driven pathfinding like maps with estimated distances, use A* algorithm. For very large graphs with dynamic changes, consider specialized algorithms like Johnson's or contraction hierarchies.

Production Patterns

In real-world systems, Dijkstra's algorithm is often used with priority queues and adjacency lists for efficient routing. It is combined with heuristics in GPS navigation to speed up searches. Network routers use variants to quickly update paths when network topology changes.

Connections

Bellman-Ford Algorithm

Alternative shortest path algorithm that handles negative weights.

Understanding Dijkstra's limitations helps appreciate why Bellman-Ford exists and when to choose it.

Priority Queue Data Structure

Core data structure used to efficiently select the next node in Dijkstra's algorithm.

Mastering priority queues deepens understanding of how Dijkstra achieves its efficiency.

Supply Chain Logistics

Real-world application domain where shortest path algorithms optimize delivery routes.

Knowing how Dijkstra relates to logistics helps see its practical impact beyond theory.

Common Pitfalls

#1 Using Dijkstra's algorithm on graphs with negative edge weights.

Wrong approach:

Run Dijkstra on a graph where some edges have negative costs without modification.

Correct approach:

Use Bellman-Ford algorithm for graphs with negative edge weights.

Root cause:

Misunderstanding that Dijkstra assumes all edge weights are non-negative for correctness.

#2 Selecting the next node to process by scanning all nodes instead of using a priority queue.

Wrong approach:

for each iteration, loop through all nodes to find the minimum distance node.

Correct approach:

Use a priority queue to efficiently get the node with the smallest tentative distance.

Root cause:

Not knowing the importance of efficient data structures for algorithm performance.

#3 Not marking nodes as visited and reprocessing them multiple times.

Wrong approach:

Allow nodes to be added repeatedly to the priority queue without checking if already visited.

Correct approach:

Keep a visited array or set to skip nodes already finalized.

Root cause:

Overlooking the need to prevent redundant work and infinite loops.

Key Takeaways

Dijkstra's algorithm finds the shortest paths from one start node to all others by always choosing the closest unvisited node next.

It requires all edge weights to be non-negative to guarantee correct results.

Using a priority queue is essential for efficient selection of the next node and overall performance.

Understanding its limitations and alternatives like Bellman-Ford helps apply the right algorithm to the right problem.

Advanced optimizations and variants make Dijkstra practical for large-scale, real-world applications.

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