Java Program to Implement Dijkstra Algorithm

You can implement Dijkstra's algorithm in Java by creating a method that uses a priority queue to find the shortest path from a source node to all other nodes in a graph, like in public void dijkstra(int[][] graph, int src) which updates distances using a min-distance selection process.

Examples

Inputgraph = {{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}}, src = 0

OutputVertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14

Inputgraph = {{0, 1, 4}, {1, 0, 2}, {4, 2, 0}}, src = 0

OutputVertex Distance from Source 0 0 1 1 2 3

Inputgraph = {{0}}, src = 0

OutputVertex Distance from Source 0 0

How to Think About It

To implement Dijkstra's algorithm, think of the graph as a map of cities connected by roads with distances. Start from the source city and keep track of the shortest known distance to each city. Repeatedly pick the city with the smallest known distance that you haven't visited yet, then update the distances to its neighbors if you find a shorter path through it. Continue until all cities have been visited.

Algorithm

1

Initialize distances from source to all vertices as infinite except source itself which is zero

2

Create a set to track vertices included in shortest path tree

3

Repeat until all vertices are processed:

4

Pick the vertex with the minimum distance not yet processed

5

Update distances of adjacent vertices if a shorter path is found through the picked vertex

6

After processing all vertices, return the distance array

Code

java

import java.util.*;

public class Dijkstra {
    static final int V = 9;

    int minDistance(int[] dist, boolean[] sptSet) {
        int min = Integer.MAX_VALUE, minIndex = -1;
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && dist[v] < min) {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }

    void dijkstra(int[][] graph, int src) {
        int[] dist = new int[V];
        boolean[] sptSet = new boolean[V];

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

        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet);
            sptSet[u] = true;

            for (int v = 0; v < V; v++) {
                if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + " \t " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = new int[][] {
            {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}
        };
        Dijkstra t = new Dijkstra();
        t.dijkstra(graph, 0);
    }
}

Output

Vertex Distance from Source
0 	 0
1 	 4
2 	 12
3 	 19
4 	 21
5 	 11
6 	 9
7 	 8
8 	 14

Dry Run

Let's trace the example graph with source 0 through the code

1

Initialize distances and sptSet

dist = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞], sptSet = [false, false, false, false, false, false, false, false, false]

2

Pick vertex with min distance not in sptSet

Pick vertex 0 (distance 0), mark sptSet[0] = true

3

Update distances of neighbors of 0

Update dist[1] = 4, dist[7] = 8

4

Pick next vertex with min distance

Pick vertex 1 (distance 4), mark sptSet[1] = true

5

Update distances of neighbors of 1

Update dist[2] = 12, dist[7] remains 8

6

Continue picking vertices and updating distances

Eventually all vertices processed with final dist array

Iteration	Picked Vertex	dist array
1	0	[0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
2	0	[0, 4, ∞, ∞, ∞, ∞, ∞, 8, ∞]
3	1	[0, 4, 12, ∞, ∞, ∞, ∞, 8, ∞]
4	7	[0, 4, 12, ∞, ∞, ∞, 9, 8, 14]
5	6	[0, 4, 12, ∞, ∞, ∞, 9, 8, 14]
6	2	[0, 4, 12, 19, ∞, 16, 9, 8, 14]
7	8	[0, 4, 12, 19, ∞, 16, 9, 8, 14]
8	3	[0, 4, 12, 19, 21, 16, 9, 8, 14]
9	5	[0, 4, 12, 19, 21, 11, 9, 8, 14]
10	4	[0, 4, 12, 19, 21, 11, 9, 8, 14]

Why This Works

Step 1: Initialize distances

Set all distances to infinity except the source which is zero to start with no known paths.

Step 2: Select minimum distance vertex

Pick the vertex with the smallest distance not yet processed to ensure shortest paths are built step-by-step.

Step 3: Update neighbors

Check neighbors of the picked vertex and update their distances if a shorter path is found through it.

Step 4: Repeat until done

Continue selecting vertices and updating distances until all vertices are processed, resulting in shortest paths.

Alternative Approaches

Using PriorityQueue for optimization

java

import java.util.*;

public class DijkstraPQ {
    static class Node implements Comparable<Node> {
        int vertex, dist;
        Node(int v, int d) { vertex = v; dist = d; }
        public int compareTo(Node other) { return Integer.compare(this.dist, other.dist); }
    }

    static final int V = 9;

    void dijkstra(int[][] graph, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(src, 0));

        boolean[] visited = new boolean[V];

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.vertex;
            if (visited[u]) continue;
            visited[u] = true;

            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !visited[v] && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    pq.add(new Node(v, dist[v]));
                }
            }
        }

        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + " \t " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = new int[][] {
            {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}
        };
        new DijkstraPQ().dijkstra(graph, 0);
    }
}

This approach uses a priority queue to efficiently pick the next vertex with the smallest distance, improving performance on large graphs.

Using adjacency list instead of matrix

java

import java.util.*;

public class DijkstraList {
    static class Edge {
        int to, weight;
        Edge(int t, int w) { to = t; weight = w; }
    }

    static final int V = 9;

    void dijkstra(List<Edge>[] graph, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

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

        boolean[] visited = new boolean[V];

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

            for (Edge e : graph[u]) {
                int v = e.to, w = e.weight;
                if (!visited[v] && dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.add(new int[]{v, dist[v]});
                }
            }
        }

        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + " \t " + dist[i]);
        }
    }

    public static void main(String[] args) {
        List<Edge>[] graph = new ArrayList[V];
        for (int i = 0; i < V; i++) graph[i] = new ArrayList<>();

        graph[0].add(new Edge(1, 4)); graph[0].add(new Edge(7, 8));
        graph[1].add(new Edge(0, 4)); graph[1].add(new Edge(2, 8)); graph[1].add(new Edge(7, 11));
        graph[2].add(new Edge(1, 8)); graph[2].add(new Edge(3, 7)); graph[2].add(new Edge(5, 4)); graph[2].add(new Edge(8, 2));
        graph[3].add(new Edge(2, 7)); graph[3].add(new Edge(4, 9)); graph[3].add(new Edge(5, 14));
        graph[4].add(new Edge(3, 9)); graph[4].add(new Edge(5, 10));
        graph[5].add(new Edge(2, 4)); graph[5].add(new Edge(3, 14)); graph[5].add(new Edge(4, 10)); graph[5].add(new Edge(6, 2));
        graph[6].add(new Edge(5, 2)); graph[6].add(new Edge(7, 1)); graph[6].add(new Edge(8, 6));
        graph[7].add(new Edge(0, 8)); graph[7].add(new Edge(1, 11)); graph[7].add(new Edge(6, 1)); graph[7].add(new Edge(8, 7));
        graph[8].add(new Edge(2, 2)); graph[8].add(new Edge(6, 6)); graph[8].add(new Edge(7, 7));

        new DijkstraList().dijkstra(graph, 0);
    }
}

Using adjacency lists saves memory for sparse graphs and can be combined with a priority queue for efficient shortest path calculation.

Complexity: O(V^2) time, O(V) space

Time Complexity

The basic implementation uses nested loops over vertices, resulting in O(V^2) time. Using a priority queue and adjacency list reduces it to O(E log V).

Space Complexity

The algorithm stores distance and visited arrays of size V, so space complexity is O(V). The graph representation affects additional space.

Which Approach is Fastest?

Using a priority queue with adjacency lists is faster for sparse graphs, while the matrix approach is simpler but slower for large graphs.

Approach	Time	Space	Best For
Adjacency Matrix + Simple Loop	O(V^2)	O(V^2)	Small graphs or dense graphs
Priority Queue + Adjacency List	O(E log V)	O(V + E)	Large sparse graphs
Priority Queue + Adjacency Matrix	O(V^2 log V)	O(V^2)	Medium graphs with moderate density