Graphs

Graph Patterns: Weighted Shortest Path (Dijkstra's)

May 2026

8 min read

Standard BFS breaks down when edges have different 'costs' or 'weights'. To find the cheapest path through a weighted network, we must use Dijkstra's Algorithm.

Introduction

If a problem asks for the shortest path, but traversing different edges costs different amounts of "money," "time," or "distance", you must upgrade to Dijkstra's Algorithm.

Dijkstra’s is essentially a BFS, but instead of using a standard FIFO Queue, it uses a Priority Queue (Min-Heap).

Edge Relaxation

The core mechanism is called "Relaxation." We maintain an array of distances initialized to Infinity.

As we pull the absolute cheapest available node from our Min-Heap, we look at its neighbors. If the distance to reach the current node plus the weight of the edge to the neighbor is strictly less than the neighbor's currently recorded distance, we "relax" (update) the distance and push the neighbor back into the Priority Queue.

Implementation

java

class Solution {
    // Edge structure: {targetNode, weight}
    public int[] dijkstra(int V, ArrayList<ArrayList<int[]>> adj, int src) {
        // Min-Heap: {distance, node}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        dist[src] = 0;
        pq.add(new int[]{0, src});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int d = current[0];
            int node = current[1];
            
            // Minor optimization: Skip if we found a better path already
            if (d > dist[node]) continue;
            
            for (int[] edge : adj.get(node)) {
                int neighbor = edge[0];
                int weight = edge[1];
                
                // Edge Relaxation
                if (dist[node] + weight < dist[neighbor]) {
                    dist[neighbor] = dist[node] + weight;
                    pq.add(new int[]{dist[neighbor], neighbor});
                }
            }
        }
        return dist;
    }
}