Dijkstra Algorithm

Intuition

Greedy shortest path: always extend the unvisited node with the smallest current distance. Use a min-heap (priority queue) to efficiently get the next minimum. Only works with non-negative edge weights.

Algorithm

1dist[src]=0, all others=INF. Add (0,src) to min-heap.
2While heap not empty: extract (d,u). If d > dist[u], skip (stale entry).
3For each neighbor (v,w): if dist[u]+w < dist[v]: dist[v]=dist[u]+w. Push (dist[v],v).

Example Walkthrough

Input: V=5, edges: 0â†’1(4),0â†’2(1),2â†’1(2),1â†’3(1),2â†’3(5)

1.dist=[0,âˆž,âˆž,âˆž,âˆž]. Process 0: dist[1]=4, dist[2]=1.
2.Process 2(d=1): dist[1]=min(4,3)=3, dist[3]=6.
3.Process 1(d=3): dist[3]=min(6,4)=4.

Output: dist=[0,3,1,4,âˆž]

Common Pitfalls

•Skip stale heap entries by checking if extracted distance > dist[u].

Dijkstra Algorithm.java

Java

// Approach: Min-heap Dijkstra. Extract minimum distance node, relax neighbors, update distances.
// Time: O((V+E) log V) Space: O(V)
import java.util.*;

class Solution {
    public int[] dijkstra(int V, int[][] edges, int src) {
        // Create adjacency list: node -> list of (neighbor, weight)
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Since it's an undirected graph, add both directions
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            adj.get(u).add(new int[] { v, w });
            adj.get(v).add(new int[] { u, w });
        }

        // Distance array, initialized with "infinity"
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        // Min-heap priority queue: stores (distance, node)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[] { 0, src });

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currDist = current[0];
            int u = current[1];

            // Traverse all adjacent vertices
            for (int[] neighbor : adj.get(u)) {
                int v = neighbor[0];
                int weight = neighbor[1];

                if (currDist + weight < dist[v]) {
                    dist[v] = currDist + weight;
                    pq.add(new int[] { dist[v], v });
                }
            }
        }

        return dist;
    }
}

Was this solution helpful?