Contents
- How Dijkstra's algorithm works
- Implementation
- Complexity Analysis
- Limitations
The core idea is to maintain a distance array where dist[v] represents the shortest
known distance from the source to node v. Initially all distances are set to infinity (∞),
except for the source node which is set to 0.
A Min-Heap (Priority Queue) is used to always pick the unvisited node with the smallest current distance.
Algorithm steps:
- Initialise dist[source] = 0 and dist[v] = ∞ for all other nodes.
- Add the source node to the priority queue with distance 0.
- While the priority queue is not empty:
- Extract the node u with the minimum distance.
- For each neighbour v of u, calculate newDist = dist[u] + weight(u, v).
- If newDist < dist[v], update dist[v] = newDist and add v to the priority queue.
- When the priority queue is empty, dist[] holds the shortest distance from source to every node.
Dijkstra's algorithm does not work correctly with negative edge weights.
For graphs with negative weights, use the Bellman-Ford algorithm instead.
Below implementation uses an adjacency list to represent the graph and a PriorityQueue (min-heap)
to always process the node with the currently smallest known distance.
import java.util.*;
public class Dijkstra {
// Edge: destination node and weight
static class Edge {
int dest, weight;
Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
/**
* Finds shortest distances from source to all nodes.
* @param graph adjacency list: graph[u] = list of Edge(v, w)
* @param V number of vertices
* @param source starting node
* @return dist[] array where dist[i] = shortest distance from source to i
*/
public int[] dijkstra(List<List<Edge>> graph, int V, int source) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
// Min-heap: (distance, node)
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, source});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
// Skip if we already found a better path
if (d > dist[u]) continue;
for (Edge edge : graph.get(u)) {
int newDist = dist[u] + edge.weight;
if (newDist < dist[edge.dest]) {
dist[edge.dest] = newDist;
pq.offer(new int[]{newDist, edge.dest});
}
}
}
return dist;
}
}
Example usage:
int V = 5; // 5 nodes: 0, 1, 2, 3, 4
List<List<Dijkstra.Edge>> graph = new ArrayList<>();
for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
// Add edges: (from, to, weight)
graph.get(0).add(new Dijkstra.Edge(1, 4));
graph.get(0).add(new Dijkstra.Edge(2, 1));
graph.get(2).add(new Dijkstra.Edge(1, 2));
graph.get(1).add(new Dijkstra.Edge(3, 1));
graph.get(2).add(new Dijkstra.Edge(3, 5));
graph.get(3).add(new Dijkstra.Edge(4, 3));
Dijkstra d = new Dijkstra();
int[] distances = d.dijkstra(graph, V, 0);
System.out.println(Arrays.toString(distances));
// Output: [0, 3, 1, 4, 7]
// Shortest distances from node 0 to all other nodes
-
Time complexity: O((V + E) log V) — each vertex is extracted from the priority queue once
(O(V log V)) and each edge is relaxed once (O(E log V)).
-
Space complexity: O(V + E) — for the distance array, priority queue, and adjacency list.
-
No negative edge weights — Dijkstra assumes all weights are non-negative.
A negative weight can cause the algorithm to produce incorrect results because a previously finalised node
might actually be reachable via a cheaper path through a negative edge.
-
Single-source only — Dijkstra computes shortest paths from one source node.
For all-pairs shortest paths, use Floyd-Warshall or run Dijkstra from every node.