Implement Dijkstra's Algorithm in Java
Problem
Dijkstra's algorithm finds the shortest distance from a starting node to every other node in a graph whose edge weights are not negative.
Given five places joined by roads of different lengths, find the shortest distance and route from A to each of the others.
Java Program
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class DijkstraShortestPath {
public static void main(String[] args) {
String[] names = {"A", "B", "C", "D", "E"};
int n = names.length;
List<List<int[]>> graph = new ArrayList<>(); // graph.get(u) holds {neighbour, weight}
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
int[][] edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {3, 4, 3}};
for (int[] e : edges) {
graph.get(e[0]).add(new int[]{e[1], e[2]});
graph.get(e[1]).add(new int[]{e[0], e[2]}); // undirected roads
}
int[] dist = new int[n];
int[] prev = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(prev, -1);
dist[0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[1], y[1])); // {node, distance}
pq.add(new int[]{0, 0});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int u = top[0];
if (top[1] > dist[u]) continue; // stale entry: a shorter route was already found
for (int[] edge : graph.get(u)) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) { // relax the edge
dist[v] = dist[u] + w;
prev[v] = u;
pq.add(new int[]{v, dist[v]});
}
}
}
for (int v = 1; v < n; v++) {
StringBuilder path = new StringBuilder(names[v]);
for (int at = prev[v]; at != -1; at = prev[at]) path.insert(0, names[at] + " -> ");
System.out.println("A to " + names[v] + ": " + dist[v] + " via " + path);
}
}
}Output
Core Logic
Always expand the closest node not yet finalised; because no edge is negative, its current distance can't be improved later, so it's settled for good.
- 1
diststarts at infinity for every node except A, which is 0. - 2A priority queue hands back the node with the smallest known distance.
- 3For each neighbour, if going through the current node is shorter, the distance and
prevare updated and the neighbour is queued — this is called relaxing the edge. - 4Entries whose distance is larger than the recorded one are stale and skipped; following
prevbackwards rebuilds each route.
Key Point: With a negative edge, a node settled early might later be reachable more cheaply, so the result can be wrong — use Bellman-Ford for graphs with negative weights.
Why: Each edge can add one queue entry, and each queue operation costs log V; the graph and distance arrays take V + E space.
Key Concepts
Approach 2: Array-Based Version (No Priority Queue)
import java.util.Arrays;
public class DijkstraArray {
public static void main(String[] args) {
final int INF = Integer.MAX_VALUE;
int[][] w = { // adjacency matrix, 0 = no direct road
{0, 4, 1, 0, 0},
{4, 0, 2, 1, 0},
{1, 2, 0, 5, 0},
{0, 1, 5, 0, 3},
{0, 0, 0, 3, 0}
};
int n = w.length;
int[] dist = new int[n];
boolean[] done = new boolean[n];
Arrays.fill(dist, INF);
dist[0] = 0;
for (int round = 0; round < n; round++) {
int u = -1;
for (int i = 0; i < n; i++) { // pick the closest unfinished node
if (!done[i] && dist[i] != INF && (u == -1 || dist[i] < dist[u])) u = i;
}
if (u == -1) break; // the rest are unreachable
done[u] = true;
for (int v = 0; v < n; v++) {
if (w[u][v] > 0 && !done[v] && dist[u] + w[u][v] < dist[v]) {
dist[v] = dist[u] + w[u][v];
}
}
}
System.out.println("Shortest distances from A: " + Arrays.toString(dist));
}
}
Output
Core Logic
The original form of the algorithm scans all nodes to find the closest unfinished one, which needs no heap at all.
- 1Roads are stored in an adjacency matrix, where 0 means no direct road.
- 2Each round picks the unfinished node with the smallest distance by scanning the array.
- 3That node is marked done, and its neighbours' distances are relaxed.
- 4The loop runs at most V rounds.
Key Point: The O(V²) array version is actually faster on dense graphs, where E is close to V²; the heap version wins on sparse road-network-style graphs.
Why: Each of V rounds scans V nodes, and the matrix stores V² entries.
Key Concepts
Interview Questions
Why can't Dijkstra's algorithm handle negative weights?
It assumes a node's distance is final once it's taken from the queue. A later negative edge could make that distance smaller, so the result would be wrong.
How is Dijkstra's algorithm different from BFS?
BFS finds shortest paths only when every edge has the same weight. Dijkstra handles different non-negative weights by always expanding the closest node first.