Problem overview
The method dijkstra receives the number of vertices n and an int[][] of edges, where each edge is [u, v, weight]. The graph is undirected and weighted, with weights from 1 to 1000, and it is connected. The method returns an array dist in which dist[i] is the length of the shortest path from vertex 0 to vertex i, where the length of a path is the sum of its edge weights.
For n = 5 and edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]], the answer is [0, 3, 1, 4, 7]. The direct edge from 0 to 1 costs 4, but going through vertex 2 costs 1 + 2 = 3. Vertex 3 is then 3 + 1 = 4 away, and vertex 4 is 4 + 3 = 7 away.
Approach: always expand the closest unfinished vertex
Breadth-first search finds shortest paths when every edge counts as one step. With weights, fewer edges don't mean a shorter path, as the example shows. Dijkstra's algorithm fixes this by choosing the next vertex by distance and not by arrival order.
The algorithm keeps a table dist of the best distances found so far. It starts with dist[0] = 0 and everything else at "infinity". It then repeats: take the vertex with the smallest known distance, and for each edge leaving it, check whether going through this vertex gives a neighbor a better distance. This check is called relaxing the edge. When a neighbor improves, it is put on a to-do list with its new distance.
It works because all weights are positive. The vertex with the smallest tentative distance can't be improved later: any other route to it would have to pass through a vertex that is at least as far away, and then add more positive weight. So when a vertex is taken from the front of the to-do list, its distance is final.
The to-do list is a priority queue, which always hands out the entry with the smallest distance first. Java's PriorityQueue has no operation to lower the priority of an entry already inside. The lesson's approach is to add a new entry with the better distance and to ignore the outdated entry when it eventually comes out. This is called lazy deletion.
Step by step
- Create the adjacency list: an array
adjof lists, with oneArrayListper vertex. Each entry inadj[i]is a smallint[]pair,{neighbor, weight}. - Fill it from
edges. The graph is undirected, so each edge is stored twice:{e[1], e[2]}in the list ofe[0], and{e[0], e[2]}in the list ofe[1]. - Create
dist, filled withInteger.MAX_VALUEto mean "not reached yet", and setdist[0]to 0. - Create the priority queue of
int[]pairs{distance, vertex}, ordered by the first value with the comparator(a, b) -> a[0] - b[0]. Arrays have no natural order, so the comparator is required. Offer the pair{0, 0}for the source. - Loop while the queue is not empty.
- Poll the closest entry and unpack it:
dis the distance recorded in the entry anduis the vertex. - Skip stale entries: if
d > dist[u], a shorter path touwas found after this entry was added, socontinue. - Loop over the neighbors of
uinadj[u]. - Relax each edge. With
vandwunpacked from the pair, ifdist[u] + w < dist[v], setdist[v]to that sum and offer{dist[v], v}. Only improvements are queued. - Return
dist. Once the queue is empty, every distance is final.
The solution in Java
class Solution {
public int[] dijkstra(int n, int[][] edges) {
List<int[]>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<>();
}
for (int[] e : edges) {
adj[e[0]].add(new int[]{e[1], e[2]});
adj[e[1]].add(new int[]{e[0], e[2]});
}
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
if (d > dist[u]) {
continue;
}
for (int[] neighbor : adj[u]) {
int v = neighbor[0], w = neighbor[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}
}
On the example, the queue starts with {0, 0}. Processing vertex 0 sets dist[1] = 4 and dist[2] = 1. The entry for vertex 2 comes out next and improves vertex 1 to 3, vertex 3 to 6. Then the entry {3, 1} improves vertex 3 to 4. When the old entries {4, 1} and {6, 3} come out later, d > dist[u] is true and they are skipped. Vertex 4 ends at 7.
Java details worth a closer look:
- An array of lists needs the raw type. Java can't create an array of a generic type, so
new ArrayList[n]is assigned to aList<int[]>[]. The compiler warns about an unchecked conversion, but the code is fine. The slots start asnull, which the first loop fixes. PriorityQueueand comparators. The queue is a min-heap:pollreturns the entry the comparator ranks first. Subtracting in a comparator can overflow with large values.Integer.compare(a[0], b[0])is the safe form. Here distances stay small enough for either.- Why
Integer.MAX_VALUEis safe. The sumdist[u] + wis only computed for a vertexutaken from the queue, which has a real distance. AddingwtoMAX_VALUEwould wrap around to a negative number, but that never happens. - Declaring several variables.
int d = curr[0], u = curr[1];declares twoints in one line. Both come from the pair stored in the queue.
Complexity
Let m be the number of edges.
Time: O((n + m) log m). Each edge is relaxed at most twice (once from each end), and each successful relaxation adds one queue entry, so the queue sees at most 2m + 1 entries. Adding and removing an entry each cost O(log m). For a graph without parallel edges, log m is O(log n), so the bound is often written O((n + m) log n).
Space: O(n + m). The adjacency lists hold 2m pairs, dist holds n values, and the queue holds at most 2m + 1 entries.
Edge cases and common mistakes
- Negative weights. Dijkstra's argument needs every weight to be non-negative. Here weights are at least 1. With negative edges, a vertex taken from the queue could still be improved, so another algorithm is needed.
- Skipping the stale-entry check. The answer stays correct, but outdated entries then repeat all their relaxations. On dense graphs this wastes much time.
- Adding edges in one direction. The graph is undirected. Without the second
add, vertices only reachable "backwards" along a listed edge would keepInteger.MAX_VALUE. - Forgetting to set
dist[0] = 0. Every distance would then start at infinity, and no relaxation could ever succeed. - A comparator on the wrong field. The queue must order by distance, which is
a[0]in this layout. Ordering by the vertex number would still terminate, but it isn't Dijkstra's order and would repeat work. - Unreachable vertices. The lesson guarantees a connected graph. If a vertex were unreachable, its entry would stay at
2147483647, which isInteger.MAX_VALUE. - Parallel edges and cycles. Both are fine: a worse edge simply fails the
<test, and a cycle can't improve any distance when all weights are positive.
Testing
n = 5,edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]]gives[0, 3, 1, 4, 7].n = 2,edges = [[0,1,7]]gives[0, 7].n = 3,edges = [[0,1,5],[0,1,2],[1,2,1]]gives[0, 2, 3].