DSA Javaprogramming

Dijkstra's Algorithm Single Source Shortest Path in DSA Java

Choose your learning style10 modes available

Learn Why Deep Visual Try Challenge Project Recall Time

Mental Model

Find the shortest path from one starting point to all other points by always choosing the closest unvisited point next.

Analogy: Imagine you are in a city and want to find the shortest way to every other place. You start from your home and always visit the nearest new place you haven't been to yet, updating the shortest known routes as you go.

Graph nodes with distances:

  (A)
 /   \
5     2
/       \
(B)---1--(C)

Start at A with distance 0, others unknown (∞).

Dry Run Walkthrough

Input: Graph with nodes A, B, C and edges: A-B=5, A-C=2, B-C=1; start at A

Goal: Find shortest distances from A to all nodes

Step 1: Start at A, set distance to A=0, others ∞

Distances: A=0, B=∞, C=∞; Visited: none

Why: We know distance to start is zero, others unknown

Step 2: Visit nearest unvisited node: C (distance 2)

Distances: A=0, B=5, C=2; Visited: A

Why: C is closest to A, so we explore paths from C next

Step 3: Update distance to B via C: min(5, 2+1)=3

Distances: A=0, B=3, C=2; Visited: A, C

Why: Going A->C->B is shorter than previous 5

Step 4: Visit next nearest unvisited node: B (distance 3)

Distances: A=0, B=3, C=2; Visited: A, C, B

Why: B is now the closest unvisited node

Step 5: All nodes visited, shortest distances found

Distances: A=0, B=3, C=2; Visited: A, B, C

Why: Algorithm ends when all nodes are visited

Result:

Shortest distances from A: A=0 -> B=3 -> C=2

Annotated Code

DSA Java

import java.util.*;

class Graph {
    private final Map<String, List<Edge>> adj = new HashMap<>();

    static class Edge {
        String target;
        int weight;
        Edge(String target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }

    void addEdge(String source, String target, int weight) {
        adj.computeIfAbsent(source, k -> new ArrayList<>()).add(new Edge(target, weight));
        adj.computeIfAbsent(target, k -> new ArrayList<>()); // Ensure target node exists
    }

    Map<String, Integer> dijkstra(String start) {
        Map<String, Integer> dist = new HashMap<>();
        for (String node : adj.keySet()) {
            dist.put(node, Integer.MAX_VALUE);
        }
        dist.put(start, 0);

        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
        pq.offer(new AbstractMap.SimpleEntry<>(start, 0));

        Set<String> visited = new HashSet<>();

        while (!pq.isEmpty()) {
            Map.Entry<String, Integer> current = pq.poll();
            String currNode = current.getKey();
            if (visited.contains(currNode)) continue;
            visited.add(currNode);

            for (Edge edge : adj.get(currNode)) {
                if (visited.contains(edge.target)) continue;
                int newDist = dist.get(currNode) + edge.weight;
                if (newDist < dist.get(edge.target)) {
                    dist.put(edge.target, newDist);
                    pq.offer(new AbstractMap.SimpleEntry<>(edge.target, newDist));
                }
            }
        }
        return dist;
    }
}

public class DijkstraDemo {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge("A", "B", 5);
        g.addEdge("A", "C", 2);
        g.addEdge("B", "C", 1);

        Map<String, Integer> distances = g.dijkstra("A");
        for (String node : distances.keySet()) {
            System.out.println("Distance from A to " + node + " = " + distances.get(node));
        }
    }
}

dist.put(start, 0);

Initialize start node distance to zero

pq.offer(new AbstractMap.SimpleEntry<>(start, 0));

Add start node to priority queue with distance zero

Map.Entry<String, Integer> current = pq.poll();

Extract node with smallest distance from queue

if (visited.contains(currNode)) continue;

Skip nodes already processed

visited.add(currNode);

Mark current node as visited

for (Edge edge : adj.get(currNode)) {

Check all neighbors of current node

int newDist = dist.get(currNode) + edge.weight;

Calculate new possible distance to neighbor

if (newDist < dist.get(edge.target)) {

If new distance is shorter, update it

dist.put(edge.target, newDist);

Update shortest distance to neighbor

pq.offer(new AbstractMap.SimpleEntry<>(edge.target, newDist));

Add neighbor to queue with updated distance

OutputSuccess

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

Complexity Analysis

Time: O(E log V) because each edge is checked and priority queue operations take log V time

Space: O(V + E) to store graph and distance data

vs Alternative: Compared to Bellman-Ford's O(VE), Dijkstra is faster on graphs without negative edges

Edge Cases

Graph with isolated nodes (no edges)

Distances to isolated nodes remain infinite (unreachable)

DSA Java

dist.put(start, 0);

Graph with single node

Distance to start node is zero, no other nodes to process

DSA Java

dist.put(start, 0);

Graph with multiple edges between same nodes

Algorithm picks shortest edge automatically by updating distances

DSA Java

if (newDist < dist.get(edge.target)) {

When to Use This Pattern

When you need shortest paths from one point to all others in a graph with non-negative weights, use Dijkstra's algorithm because it efficiently finds minimum distances.

Common Mistakes

Mistake: Not marking nodes as visited and revisiting them endlessly
Fix: Add a visited set and skip nodes already processed

Mistake: Using a normal queue instead of a priority queue
Fix: Use a priority queue to always pick the closest unvisited node

Mistake: Not updating distances when a shorter path is found
Fix: Check and update distances only if new path is shorter

Summary

Finds shortest distances from one start node to all others in a weighted graph.

Use when you want efficient shortest paths and all edge weights are non-negative.

Always pick the closest unvisited node next and update neighbors' distances.

Practice

(1/5)

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

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Dijkstra's Algorithm Single Source Shortest Path in DSA Java

Practice

Solution

Step 1: Understand the algorithm's goal

Step 2: Compare with other graph algorithms

Final Answer:

Quick Check:

Solution

Step 1: Identify the need for efficient minimum selection

Step 2: Match data structures to this need

Final Answer:

Quick Check:

Solution

Step 1: Initialize distances and process vertices

Step 2: Calculate shortest distances

Final Answer:

Quick Check:

Solution

Step 1: Understand PriorityQueue usage

Step 2: Identify missing priority update

Final Answer:

Quick Check:

Solution

Step 1: Recall Dijkstra's requirements

Step 2: Impact of zero weights

Final Answer:

Quick Check:

Ready to prove it?