Algorithms

Pathfinding: Dijkstra's Shortest Path Logic

Mar 2026

9 min read

Dijkstra solves the single-source shortest path problem. It serves as the backbone for GPS navigation and network routing protocols.

Implementation

java

public int[] dijkstra(int V, List<List<int[]>> adj, int S) {
    int[] dist = new int[V];
    Arrays.fill(dist, (int)1e9);
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    dist[S] = 0;
    pq.add(new int[]{0, S});

    while (!pq.isEmpty()) {
        int d = pq.peek()[0];
        int node = pq.peek()[1];
        pq.poll();

        for (int[] it : adj.get(node)) {
            int v = it[0];
            int wt = it[1];
            if (d + wt < dist[v]) {
                dist[v] = d + wt;
                pq.add(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}