Problem overview
The method dijkstra receives n, the number of vertices (labeled 0 to n-1), and edges, an Array[Array[Int]] where each entry is [u, v, weight]. The graph is undirected and connected, and every weight is at least 1. The method returns an Array[Int] of length n in which position i holds the length of the shortest path from vertex 0 to vertex i.
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 0, 2, 1 costs 1 + 2 = 3, so the longer route in edge count is the shorter one in weight. That is why a plain breadth-first search is not enough: weights make "fewest edges" and "smallest total" different things.
Approach: always expand the closest unfinished vertex
Dijkstra's algorithm keeps a tentative distance for every vertex and repeatedly takes the vertex with the smallest tentative distance among those it still has to process. Because all weights are positive, no later path can improve that vertex: any other route to it must first pass through a vertex that is at least as far away. Its distance is final, so the algorithm looks at each outgoing edge and checks whether going through this vertex gives a neighbor a shorter route. That check is called relaxing the edge.
This lesson uses the "lazy deletion" form. The queue holds (distance, vertex) pairs. When a shorter route to a vertex is found, a new pair is added and the old one stays in the queue. When the old pair is later taken out, its distance is larger than the vertex's current best, so it is recognised as stale and skipped.
The queue here is an ArrayBuffer that is searched linearly for its smallest entry, rather than a heap. It is the simplest correct version, and it fits the lesson's limits (at most 1000 vertices and 5000 edges).
Following the example
The queue starts as [(0, 0)]. Taking (0, 0) sets vertex 1 to 4 and vertex 2 to 1. Next comes (1, 2): vertex 1 improves to 3 (1 + 2) and vertex 3 gets 6. Then (3, 1) improves vertex 3 to 4. The pair (4, 1) comes out next, but vertex 1 already has distance 3, so it is stale and ignored. Then (4, 3) gives vertex 4 the distance 7, and the remaining entries, (6, 3) and (7, 4), produce no improvements.
Step by step
- Build the adjacency lists.
Array.fill(n)(...)runs its second argument once per slot, so every vertex gets its own emptyArrayBuffer[(Int, Int)]of(neighbor, weight)pairs. WritingArray.fill(n)(someBuffer)with one existing buffer would share it among all vertices. - Add each edge in both directions. The graph is undirected, so the edge
[u, v, w]goes into the list ofuand into the list ofv. The double parentheses in+= ((e(1), e(2)))pass one tuple. With single parentheses, Scala reads two separate arguments. - Create
dist. Every entry starts atInt.MaxValue, meaning "not reached yet", anddist(0)is set to 0. - Seed the queue with
(0, 0): distance first, then vertex, so a pair can be compared by its first component. - Loop while the queue is not empty. Every reachable vertex is eventually processed.
- Pick the smallest entry.
minByoverpq.indicesfinds the index of the smallest distance, andpq.remove(idx)removes that entry and returns it, whichval (d, u)unpacks. The rest of the loop body sits insideif (d <= dist(u)), which skips stale entries. Scala has nocontinue, so the check wraps the work instead of jumping past it. - Visit each neighbor of
u, unpacking the pair intovandw. - Relax the edge. If
dist(u) + w < dist(v), store the better distance and append(dist(v), v)to the queue. Adding an entry only on a real improvement keeps the queue from filling with useless pairs. - Return
dist. It is the last expression of the method, so noreturnis needed.
The solution in Scala
class Solution {
def dijkstra(n: Int, edges: Array[Array[Int]]): Array[Int] = {
val adj = Array.fill(n)(scala.collection.mutable.ArrayBuffer[(Int, Int)]())
for (e <- edges) {
adj(e(0)) += ((e(1), e(2)))
adj(e(1)) += ((e(0), e(2)))
}
val dist = Array.fill(n)(Int.MaxValue)
dist(0) = 0
val pq = scala.collection.mutable.ArrayBuffer[(Int, Int)]((0, 0))
while (pq.nonEmpty) {
val idx = pq.indices.minBy(j => pq(j)._1)
val (d, u) = pq.remove(idx)
if (d <= dist(u)) {
for ((v, w) <- adj(u)) {
if (dist(u) + w < dist(v)) {
dist(v) = dist(u) + w
pq += ((dist(v), v))
}
}
}
}
dist
}
}
Scala details worth a closer look:
- Overflow cannot happen in
dist(u) + w.Intis 32 bits and wraps silently:Int.MaxValue + 1is-2147483648. Only a vertex whose distance is already finite is ever expanded, sodist(u)is neverInt.MaxValuewhen the sum is computed. The largest real distance is under 1000 * 999. - Destructuring.
val (d, u) = pq.remove(idx)andfor ((v, w) <- adj(u))both match tuples against patterns, and give names to the parts in one line. - Index versus value.
pq.indices.minBy(j => pq(j)._1)returns the position of the smallest entry, not the entry itself. The position is needed becauseremovetakes an index.._1reads the first element of a tuple. valwith mutable contents.val distfixes the reference to the array, not its elements, sodist(v) = ...is allowed. Arrays are indexed with parentheses in Scala.- Mutable collections.
ArrayBufferlives inscala.collection.mutable, which the solution spells out in full instead of importing.
Complexity
Time: O(E²) in the worst case, where E is the number of edges. An edge is relaxed at most once in each direction, because a vertex is expanded only once with its final distance. That bounds the queue to about 2E + 1 entries over the whole run. Each removal scans the queue to find the minimum and shifts the elements after it, so it costs time proportional to the queue's current size. With a binary heap instead of a linear scan, the same algorithm runs in O(E log E).
Space: O(V + E). The adjacency lists hold two entries per edge, dist holds one number per vertex, and the queue holds at most about 2E + 1 pairs.
Edge cases and common mistakes
- Parallel edges. With edges
[0,1,5]and[0,1,2]between the same pair, relaxation keeps the cheaper one.n = 3with those edges plus[1,2,1]gives[0, 2, 3]. - Two vertices.
n = 2with the edge[0,1,7]gives[0, 7]. - Forgetting the second direction. Adding each edge to only one list treats the graph as directed and leaves some vertices unreachable at
Int.MaxValue. - Skipping the stale check. Without
d <= dist(u), outdated entries still expand their vertex. The answer stays correct, but the work grows. - Zero or negative weights. The correctness argument needs weights that are not negative. A negative edge can make an already finished vertex improve, and this algorithm never revisits it. The lesson's weights are at least 1.
- Sharing one buffer. Filling the array with the same buffer object makes every vertex's neighbor list the same list.
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].
