Problem overview
The function dijkstra receives n, the number of vertices labeled 0 to n - 1, and edges, an Array<IntArray> in which each entry is [u, v, weight]: an undirected edge between u and v with a positive weight. It returns an IntArray in which entry i is the length of the shortest path from vertex 0 to vertex i, where a path's length is the sum of its edge weights. The graph is connected, so every vertex is reachable.
For n = 5 and edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]] the result is [0, 3, 1, 4, 7]. The direct edge from 0 to 1 costs 4, but going 0, 2, 1 costs 1 + 2 = 3. Vertex 3 is then reached through 1 at cost 3 + 1 = 4, cheaper than through 2 at 1 + 5 = 6, and vertex 4 costs 4 + 3 = 7.
Approach: always expand the closest unfinished vertex
With equal weights, a breadth-first search finds shortest paths, but here a path with more edges can be cheaper than one with fewer. Dijkstra's algorithm handles weights, as long as none is negative, with one rule: always process next the vertex with the smallest known distance. Once that vertex is taken, its distance can't be improved. Any other route to it would have to pass through a vertex that is at least as far away, and weights are positive, so such a route can't be shorter.
The algorithm keeps a dist array of the best distances found so far, starting at "infinity" for every vertex except the source. Taking a vertex u, it relaxes each edge from u to a neighbour v with weight w: if dist[u] + w is smaller than dist[v], a better route to v has been found, so dist[v] is updated and v is queued with its new distance.
A real priority queue can't update an entry in place, so the usual trick, and the one in this lesson, is lazy deletion. The improved pair is simply added as a new entry, and when an old, worse entry for the same vertex comes out later, it is recognized as stale and skipped.
This lesson keeps the "priority queue" as a plain list of [distance, vertex] pairs and sorts it by distance before every removal. It's simple and fast enough for the limits of the lesson, up to 1,000 vertices and 5,000 edges.
Step by step
- Build the adjacency list.
adjis an array ofnempty lists ofIntArray, one per vertex. The initializer lambda runs once per index, so every vertex gets its own list. - Add each edge to both endpoints. The graph is undirected, so
adj[e[0]]receives the pair[e[1], e[2]]andadj[e[1]]receives[e[0], e[2]]. Each pair is a neighbour and the weight to reach it. - Create
dist. AnIntArrayfilled withInt.MAX_VALUEmarks every vertex as unreached, anddist[0]is set to 0. - Create the working list
pqholding the pair[0, 0], distance first so that sorting by the first element orders by distance. - Loop while
pqis not empty. Every reachable vertex is eventually handled. - Take the closest entry. Sort
pqby distance, remove its first pair intocur, and readdandufrom it. Ifdis larger thandist[u], the entry is stale, so skip it withcontinue. - Loop over
adj[u]withnbas each neighbour entry. - Relax the edge. Read
vandwfromnb. Ifdist[u] + w < dist[v], updatedist[v]and add the pair[dist[v], v]topq. Adding only on a real improvement keeps the list from filling with useless entries. - Return
dist. When the list is empty, every recorded distance is final.
The solution in Kotlin
class Solution {
fun dijkstra(n: Int, edges: Array<IntArray>): IntArray {
val adj = Array(n) { mutableListOf<IntArray>() }
for (e in edges) {
adj[e[0]].add(intArrayOf(e[1], e[2]))
adj[e[1]].add(intArrayOf(e[0], e[2]))
}
val dist = IntArray(n) { Int.MAX_VALUE }
dist[0] = 0
val pq = mutableListOf(intArrayOf(0, 0))
while (pq.isNotEmpty()) {
pq.sortBy { it[0] }
val cur = pq.removeAt(0)
val d = cur[0]
val u = cur[1]
if (d > dist[u]) {
continue
}
for (nb in adj[u]) {
val v = nb[0]
val w = nb[1]
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w
pq.add(intArrayOf(dist[v], v))
}
}
}
return dist
}
}
The Kotlin details worth a closer look:
mutableListOf(intArrayOf(0, 0))creates aMutableList<IntArray>that starts with one element. Its type is inferred from that element.sortBy { it[0] }sorts a mutable list in place, using the value the lambda returns as the key. Inside a lambda with one parameter,itis the current element, here a pair, soit[0]is its distance. The sort is stable.removeAt(0)removes and returns the element at index 0, which after the sort is the closest one. On a list, removing from the front shifts all later elements, but with this input size that is cheap.continueskips the rest of the currentwhileiteration and jumps back to the loop condition.- No overflow from
Int.MAX_VALUE. Only vertices that have already been reached are expanded, sodist[u]is always a real distance whendist[u] + wis computed. Adding a weight toInt.MAX_VALUEitself would wrap to a negative number, becauseIntoverflow is silent. - Pairs as
IntArray. The adjacency entries hold[neighbour, weight]and the queue entries hold[distance, vertex], so the order of fields differs between them.
Complexity
Time. Each edge is relaxed from each endpoint at most once, because a vertex is only expanded when its entry is not stale, so the list never holds more than about 2E + 1 entries, where E is the number of edges. With a heap-based priority queue the total cost is O(E log V). This lesson sorts the whole list on every iteration, so each of up to about 2E iterations costs up to O(E log E), which gives O(E² log E) in the worst case. For the lesson's limits that is fine, and the sort is quick on a list that is nearly sorted already. On a large graph, replace the list with java.util.PriorityQueue, which Kotlin on the JVM can use directly.
Space: O(V + E). The adjacency lists hold two entries per edge, dist holds V numbers, and the list of pending entries holds up to about 2E.
Edge cases and common mistakes
- A cheaper detour.
n = 3with edges[[0, 1, 1], [1, 2, 1], [0, 2, 5]]returns[0, 1, 2]: vertex 2 is reached through vertex 1 for 2, not directly for 5. - Parallel edges. With
[[0, 1, 5], [0, 1, 2], [1, 2, 1]]the result is[0, 2, 3]. The cheaper of the two edges wins, and the second relaxation overrides the first. - Self-loops. An edge such as
[0, 0, 1]never improves any distance, sincedist[0] + 1is not less thandist[0]. - Forgetting the stale check. Without
if (d > dist[u]) continue, outdated entries are expanded again. The distances stay correct, but the work grows. - Adding only one direction. The graph is undirected. Storing an edge in just one list leaves some vertices unreachable in the search.
- Unreachable vertices. The lesson guarantees none, but with
n = 3and the single edge[0, 1, 1]the code returns2147483647for vertex 2, the untouchedInt.MAX_VALUE. - Negative weights. The "a taken vertex is final" reasoning needs non-negative weights. The lesson's weights are at least 1.
Testing
n = 5,[[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,[[0, 1, 7]]gives[0, 7].n = 3,[[0, 1, 1], [1, 2, 1], [0, 2, 5]]gives[0, 1, 2].n = 3,[[0, 1, 5], [0, 1, 2], [1, 2, 1]]gives[0, 2, 3].n = 3,[[0, 0, 1], [0, 1, 3], [1, 2, 3]]gives[0, 3, 6].