Shortest Path in Weighted Undirected Graph

Link : GFG - Shortest Path in Weighted Undirected Graph

Problem Statement

You are given a weighted undirected graph consisting of N vertices and M edges. The task is to find the shortest path from vertex 0 to all other vertices using Dijkstra’s algorithm.

Input

• N: Number of vertices

• M: Number of edges

• Each edge is defined as: u, v, wt where there’s an edge between u and v with weight wt.

Output

• Return a list of shortest distances from vertex 0 to all other vertices.

• If any node is unreachable, return -1 for that node.

Constraints

• 1 <= N <= 1000

• 1 <= M <= (N*(N-1))/2

• 1 <= wt <= 1000

Intuition

This is a classic Single Source Shortest Path problem in graphs with non-negative weights, making Dijkstra's Algorithm the ideal solution.

• We need to compute minimum distances from source node 0.

• Since weights are involved, BFS won't work (it doesn’t consider weights).

• Dijkstra's algorithm ensures we always pick the next nearest unvisited node and expand its neighbors.

Algorithm

1. Use a Min Heap / Priority Queue to always expand the node with the smallest known distance.

2. Initialize a distance array dist[] with Infinity for all nodes, set dist[0] = 0.

3. Add (0, 0) to the priority queue: (distance, node).

4. While the priority queue is not empty:

   • Pop the node with the smallest distance.

   • For each neighbor (v, wt) of the current node:

     • If dist[u] + wt < dist[v], update dist[v] and push (dist[v], v) into the priority queue.

5. After the loop, return the dist[].

Why Priority Queue (Min Heap) Over Queue

• Queue (like BFS) processes nodes in the order they are discovered, not in order of their distance.

• Priority Queue ensures the closest node is always expanded first (Greedy).

• Set or TreeSet can be faster in deletion and update operations, but:

  • In Java, TreeSet does not allow duplicate values (needed for Dijkstra’s re-processing).

  • Also, updating a key in TreeSet is not straightforward — you have to remove and re-insert.

Hence, Java PriorityQueue (which is a binary heap) is the most practical and efficient structure for Dijkstra in Java.

Time Complexity Derivation

Let’s break it down:

• In a Min-Heap based Dijkstra:

  • You push a node to heap every time its distance is updated. In worst case, each edge might cause a push.

  • So total number of pushes = O(E)

  • Each heap operation (insert, extract) takes O(log V)

  • Hence, total time: O(E log V)

If the graph is dense, then:

• E ≈ V² → time = O(V² log V)

If the graph is sparse, then:

• E ≈ V → time = O(V log V)

Java Code (Using PriorityQueue)

class Solution {
    static class Pair {
        int node;
        int dist;
        Pair(int node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }

    static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;

        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        pq.offer(new Pair(S, 0));

        while (!pq.isEmpty()) {
            Pair curr = pq.poll();
            int u = curr.node;
            int d = curr.dist;

            for (ArrayList<Integer> neighbor : adj.get(u)) {
                int v = neighbor.get(0);
                int weight = neighbor.get(1);

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new Pair(v, dist[v]));
                }
            }
        }

        return dist;
    }
}

Dry Run

Let’s take this example:

V = 4, Edges = [[0,1,1], [0,2,4], [1,2,2], [1,3,6], [2,3,3]]

Adjacency List:

0 → (1,1), (2,4)  
1 → (0,1), (2,2), (3,6)  
2 → (0,4), (1,2), (3,3)  
3 → (1,6), (2,3)

Step-by-step:

• Init: dist[0]=0, others = ∞

• pq: [(0, 0)]

1. Pop (0,0)

   • (1,1) → dist[1]=1, push (1,1)

   • (2,4) → dist[2]=4, push (2,4)

2. Pop (1,1)

   • (2,2) → 1+2=3 < 4 → update dist[2]=3, push (2,3)

   • (3,6) → dist[3]=7, push (3,7)

3. Pop (2,3)

   • (3,3) → 3+3=6 < 7 → update dist[3]=6, push (3,6)

4. Pop (2,4) — outdated distance → skip

5. Pop (3,6)

6. Pop (3,7) — outdated → skip

Final dist[] = [0, 1, 3, 6]

🛠️ Applications of Dijkstra's Algorithm

• Network routing (shortest delay/path)

• GPS systems

• Real-time game map movement

• Bandwidth optimization

• Airline or railway scheduling

• Google Maps (shortest road route)