Implement the Dijkstra Algorithm in Java from Scratch

Dijkstra’s Algorithm is one of the most fundamental and widely used graph algorithms for finding the shortest path from a single source node to all other nodes in a weighted graph. In this blog post, we will break down how the algorithm works and implement it step-by-step using Java. You’ll also learn how to structure graph data, use a priority queue for optimal performance, and handle real-world graph problems.

1. Understanding Dijkstra’s Algorithm

Dijkstra’s algorithm maintains a set of unvisited nodes and calculates the minimum distance from the source node to each node. It uses a greedy approach, always choosing the unvisited vertex with the smallest known distance.

Problem Definition: Given a graph G = (V, E) with non-negative edge weights, and a source vertex s ∈ V, find the shortest path from s to all other vertices in V.

Key Concepts:

Graph must have non-negative weights
Uses a priority queue to select the vertex with the minimum tentative distance
Each node maintains its shortest-known distance from the source

2. Defining Graph Structures in Java

Let’s start by defining the foundational data structures that represent a graph. We’ll create classes for Edge, Node, and Graph.

class Edge {
    int target;
    int weight;

    public Edge(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }
}

class Graph {
    List<List<Edge>> adjList;

    public Graph(int numVertices) {
        adjList = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int target, int weight) {
        adjList.get(source).add(new Edge(target, weight));
    }
}

Here, we’re modelling the graph as an adjacency list, which is space-efficient and suitable for sparse graphs.

3. Implementing Dijkstra’s Algorithm

Next, we implement Dijkstra’s logic. We use Java’s PriorityQueue to always process the node with the smallest tentative distance.

class Dijkstra {
    public int[] dijkstra(Graph graph, int source) {
        int V = graph.adjList.size();
        int[] dist = new int[V];
        boolean[] visited = new boolean[V];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[1])
        );
        pq.offer(new int[]{source, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
            if (visited[u]) continue;
            visited[u] = true;

            for (Edge edge : graph.adjList.get(u)) {
                int v = edge.target;
                int weight = edge.weight;

                if (!visited[v] && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }

        return dist;
    }
}

The priority queue holds arrays of nodes and their current shortest path estimates. Whenever a shorter path to a neighbor is found, we update the distance and reinsert it into the queue for further exploration.

4. Running the Algorithm with Example Input

Let’s test the algorithm on a simple directed, weighted graph with 5 nodes:

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdge(0, 1, 10);
        g.addEdge(0, 4, 5);
        g.addEdge(1, 2, 1);
        g.addEdge(4, 1, 3);
        g.addEdge(4, 2, 9);
        g.addEdge(2, 3, 4);

        Dijkstra dj = new Dijkstra();
        int[] distances = dj.dijkstra(g, 0);

        for (int i = 0; i < distances.length; i++) {
            System.out.println("Distance from 0 to " + i + ": " + distances[i]);
        }
    }
}

Expected Output:
Distance from 0 to 0: 0
Distance from 0 to 1: 8
Distance from 0 to 2: 9
Distance from 0 to 3: 13
Distance from 0 to 4: 5

This confirms the algorithm works accurately and computes the shortest distances from source node 0.

5. Optimization Tips and Use Cases

Dijkstra’s Algorithm is highly efficient with a binary heap (used in Java’s PriorityQueue). However, for extremely large graphs, consider using a Fibonacci Heap to achieve a better amortized time complexity (though not part of standard Java libraries).

Real-world Applications:

GPS Navigation systems
Routing protocols (e.g., OSPF in networking)
Game AI (pathfinding in maps)
Scheduling shortest job/route in logistics

Tips:

Always validate that weights are non-negative before applying Dijkstra
Use an adjacency list over an adjacency matrix for performance with sparse graphs
Track predecessor nodes if you want to reconstruct the path

Conclusion

We’ve implemented Dijkstra’s algorithm from scratch in Java, explored how it works, and demonstrated it with a working example. This essential algorithm is a cornerstone of graph theory and a solid addition to any developer’s toolkit, especially in applications involving optimal routing or resource pathfinding.

Use this foundational knowledge to integrate shortest path solutions into your own applications or explore further extensions like A* or Bellman-Ford for different graph types.

Useful links: