Q15: How do you implement Dijkstra's Algorithm for Shortest Paths in Weighted Graphs?

Dijkstra's Algorithm computes shortest paths from a single source node in weighted graphs with non-negative edge weights. Initialize dist[] array filled with $infty$, with dist[src] = 0. Use a PriorityQueue storing (node, distance). Poll node with minimum distance; relax neighbors if dist[u] + weight < dist[v].

Dijkstra's Shortest Path Algorithm

import java.util.*;

public class Dijkstra {
    public static int[] shortestPath(int n, List<List<int[]>> adj, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{src, 0});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0], d = curr[1];
            if (d > dist[u]) continue;
            for (int[] edge : adj.get(u)) {
                int v = edge[0], weight = edge[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
        return dist;
    }
}

💡 Relaxes graph edge weights using a Min-PriorityQueue.

Key Takeaways

Min-PriorityQueue processes closest unvisited nodes greedy style.
Time Complexity: $O((V + E) log V)$ using Min-Heap.

Knowledge Check

Why does standard Dijkstra's Algorithm fail or enter infinite loops on graphs containing NEGATIVE edge weights?

Q15: How do you implement Dijkstra's Algorithm for Shortest Paths in Weighted Graphs?

STAY UPDATED WITH BYTES!