dijkstra-template.md

Dijkstra's Algorithm - Complete Kotlin Template

Generated by Claude Code.

Overview

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. This template provides correct, production-ready implementations for competitive programming and LeetCode problems.

Time & Space Complexity

• Time Complexity: O((V + E) log V) where V = vertices, E = edges
• Space Complexity: O(V + E) for adjacency list representation

Standard Implementation (Recommended)

This is the most commonly used implementation that handles duplicate entries in the priority queue by skipping stale entries.

fun dijkstra(n: Int, graph: Array<MutableList<Pair<Int, Int>>>, source: Int): IntArray {
    val dist = IntArray(n) { Int.MAX_VALUE }
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first }) // (distance, node)
    
    dist[source] = 0
    pq.offer(0 to source)
    
    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()
        
        // Skip if we've already found a better path
        if (d > dist[u]) continue
        
        // Relax all adjacent edges
        for ((v, weight) in graph[u]) {
            val newDist = dist[u] + weight
            if (newDist < dist[v]) {
                dist[v] = newDist
                pq.offer(newDist to v)
            }
        }
    }
    
    return dist
}

Alternative with Visited Set (Classic Approach)

This implementation uses a visited set to ensure each node is processed only once. Slightly more memory but cleaner logic.

fun dijkstraWithVisited(n: Int, graph: Array<MutableList<Pair<Int, Int>>>, source: Int): IntArray {
    val dist = IntArray(n) { Int.MAX_VALUE }
    val visited = BooleanArray(n)
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    
    dist[source] = 0
    pq.offer(0 to source)
    
    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()
        
        if (visited[u]) continue
        visited[u] = true
        
        for ((v, weight) in graph[u]) {
            if (!visited[v] && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight
                pq.offer(dist[v] to v)
            }
        }
    }
    
    return dist
}

Complete Template for LeetCode Problems

This is a comprehensive template that handles common variations and optimizations needed for competitive programming.

class Solution {
    fun dijkstra(n: Int, edges: Array<IntArray>, source: Int, target: Int = -1): IntArray {
        // Build adjacency list
        val graph = Array(n) { mutableListOf<Pair<Int, Int>>() }
        for ((u, v, w) in edges) {
            graph[u].add(v to w)
            // Add this line for undirected graphs:
            // graph[v].add(u to w)
        }
        
        val dist = IntArray(n) { Int.MAX_VALUE }
        val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
        
        dist[source] = 0
        pq.offer(0 to source)
        
        while (pq.isNotEmpty()) {
            val (d, u) = pq.poll()
            
            // Early termination if target found
            if (target != -1 && u == target) break
            
            // Skip stale entries
            if (d > dist[u]) continue
            
            for ((v, weight) in graph[u]) {
                val newDist = dist[u] + weight
                if (newDist < dist[v]) {
                    dist[v] = newDist
                    pq.offer(newDist to v)
                }
            }
        }
        
        return dist
    }
}

Key Implementation Points

1. Priority Queue Setup

• Store pairs as (distance, node) not (node, distance)
• Use compareBy { it.first } to sort by distance
• Kotlin's PriorityQueue is a min-heap by default

2. Handling Stale Entries

if (d > dist[u]) continue

This line is crucial! It skips processing nodes that have already been processed with a better distance, avoiding unnecessary work.

3. Edge Relaxation

val newDist = dist[u] + weight
if (newDist < dist[v]) {
    dist[v] = newDist
    pq.offer(newDist to v)
}

Always check if the new path is better before updating and adding to queue.

4. Graph Representation

• Use Array<MutableList<Pair<Int, Int>>> where Pair(neighbor, weight)
• For undirected graphs, add edges in both directions
• For 0-indexed problems, use nodes 0 to n-1
• For 1-indexed problems, use nodes 1 to n (waste index 0)

Common Variations

Path Reconstruction

fun dijkstraWithPath(n: Int, graph: Array<MutableList<Pair<Int, Int>>>, source: Int): Pair<IntArray, Array<Int?>> {
    val dist = IntArray(n) { Int.MAX_VALUE }
    val parent = Array<Int?>(n) { null }
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    
    dist[source] = 0
    pq.offer(0 to source)
    
    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()
        if (d > dist[u]) continue
        
        for ((v, weight) in graph[u]) {
            val newDist = dist[u] + weight
            if (newDist < dist[v]) {
                dist[v] = newDist
                parent[v] = u
                pq.offer(newDist to v)
            }
        }
    }
    
    return dist to parent
}

fun reconstructPath(parent: Array<Int?>, target: Int): List<Int> {
    val path = mutableListOf<Int>()
    var current: Int? = target
    while (current != null) {
        path.add(current)
        current = parent[current]
    }
    return path.reversed()
}

Single Target (Early Termination)

fun dijkstraToTarget(n: Int, graph: Array<MutableList<Pair<Int, Int>>>, source: Int, target: Int): Int {
    val dist = IntArray(n) { Int.MAX_VALUE }
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    
    dist[source] = 0
    pq.offer(0 to source)
    
    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()
        
        if (u == target) return d
        if (d > dist[u]) continue
        
        for ((v, weight) in graph[u]) {
            val newDist = dist[u] + weight
            if (newDist < dist[v]) {
                dist[v] = newDist
                pq.offer(newDist to v)
            }
        }
    }
    
    return -1 // No path found
}

Common Pitfalls to Avoid

1. Wrong pair order: Use (distance, node) not (node, distance)
2. Missing stale check: Always include if (d > dist[u]) continue
3. Int overflow: Be careful with Int.MAX_VALUE + weight
4. Graph indexing: Match your graph indexing (0-based vs 1-based) with problem requirements
5. Forgetting edge cases: Handle single node, no edges, unreachable nodes

When to Use Dijkstra

• ✅ Non-negative edge weights
• ✅ Single source shortest path
• ✅ Need shortest distances to all nodes or specific target
• ❌ Negative edge weights (use Bellman-Ford instead)
• ❌ Unweighted graphs (use BFS instead, it's simpler)

This template should handle 99% of Dijkstra problems you'll encounter in competitive programming!