Dijkstra Algorithm

Problem

Given an undirected, weighted graph with V vertices numbered from 0 to V-1 and E edges, represented by 2d array edges[][], where edges[i]=[u, v, w] represents the edge between the nodes u and v having w edge weight.
You have to find the shortest distance of all the vertices from the source vertex src, and return an array of integers where the ith element denotes the shortest distance between ith node and source vertex src. (Geeks)

Note: The Graph is connected and doesn't contain any negative weight edge.

Examples:

Input: V = 3, edges[][] = [[0, 1, 1], [1, 2, 3], [0, 2, 6]], src = 2
Output: [4, 3, 0]
Explanation:

Shortest Paths:
For 2 to 0 minimum distance will be 4. By following path 2 -> 1 -> 0
For 2 to 1 minimum distance will be 3. By following path 2 -> 1
For 2 to 2 minimum distance will be 0. By following path 2 -> 2

Input: V = 5, edges[][] = [[0, 1, 4], [0, 2, 8], [1, 4, 6], [2, 3, 2], [3, 4, 10]], src = 0
Output: [0, 4, 8, 10, 10]
Explanation: 

Shortest Paths: 
For 0 to 1 minimum distance will be 4. By following path 0 -> 1
For 0 to 2 minimum distance will be 8. By following path 0 -> 2
For 0 to 3 minimum distance will be 10. By following path 0 -> 2 -> 3 
For 0 to 4 minimum distance will be 10. By following path 0 -> 1 -> 4

Constraints:
1 ≤ V ≤ 10⁵

1 ≤ E = edges.size() ≤ 10⁵
0 ≤ edges[i][j] ≤ 10⁴

0 ≤ src < V

Solution

Algorithm

• Approach: This method is an optimization of BFS queue approach, but instead of a queue, we use a priority queue.

• Reason for Using a Priority Queue:

  • Consider a node x where the shortest distance from src is 10.

  • If during calculations, the queue updates the distance to 12, this value is temporarily used.

  • The node x with distance 12 is added back to the queue, affecting other connected nodes.

  • When the correct distance of 10 is processed, it adjusts everything to the shortest path.

  • Using a min-heap in a priority queue ensures we always process the shortest distance first, avoiding unnecessary recalculations with longer paths.

• Note: This method won't work for negative weights because it keeps trying to reduce the distance, leading to an infinite loop.

Time Complexity

= (Max elements present in queue) x (Poll from PQ + ne x Add to PQ)

= V x ( log(heap size) + ne x (log(heap size))

= V x (1+ ne) log(heap size)

= V x (1+V-1) log(heap size)

= V² log(heap size)

= V² log(V²)

= V² logV

= E logV

• ne - number of edges

• Heap size is V² in the case of a dense graph where each node is connected to every other node. This results in a maximum of V² edges being added to the heap.

Time - O(E logV)

Space - O(E)

Code

class Solution {
    class Pair <T>{
        T weight;
        T node;
        Pair(T weight, T node){
            this.weight = weight;
            this.node = node;
        }
    }
    public int[] dijkstra(int V, int[][] edges, int src) {
        List<List<List<Integer>>> adj = createAdjList(V, edges);
        int n = adj.size();
        int[] dist = new int[n];

        for(int i=0; i<n; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        dist[src] = 0;

        djk(adj, src, dist);

        for(int i=0; i<n; i++){
            if(dist[i]==Integer.MAX_VALUE){
                dist[i] = -1;
            }
        }
        return dist;
    }

    private void djk(List<List<List<Integer>>> adj, int src, int[] dist){

        PriorityQueue<Pair<Integer>> queue = new PriorityQueue<>((pairA, pairB) -> pairA.weight-pairB.weight);
        queue.add(new Pair(0, src));
        while(!queue.isEmpty()){
            Pair<Integer> pair = queue.poll();
            int vertex = pair.node;

            for(List<Integer> neighbour : adj.get(vertex)){
                int edgeVertex = neighbour.get(0);
                int wt = neighbour.get(1);
                if(dist[edgeVertex] > dist[vertex] + wt){
                    dist[edgeVertex] = dist[vertex] + wt;
                    queue.add(new Pair(dist[edgeVertex], edgeVertex));
                }
            }
        }
    }

    private List<List<List<Integer>>> createAdjList(int V, int[][] edges){
        List<List<List<Integer>>> adjList = new ArrayList<>();

        for(int i=0; i<V; i++){
            adjList.add(new ArrayList<>());
        }

        for(int[] edge : edges){
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            adjList.get(u).add(List.of(v, weight));
        }

        return adjList;
    }
}

Print Shortest Path

• To find the actual path, we keep track of the parent node for each vertex where we get the minimum distance.

• Using the parent node array, we can derive the shortest path.

• We start tracking from the target node and move backward to the source node.

• When we reach the source node, the parent node is the same as the source node.

• Note: While initializing the parent node array, we set the parent node of a given node to be itself.

class Solution {
    class Pair <T>{
        T weight;
        T node;
        Pair(T weight, T node){
            this.weight = weight;
            this.node = node;
        }
    }
    public List<Integer> dijkstra(int V, int[][] edges, int src, int target) {
        List<List<List<Integer>>> adj = createAdjList(V, edges);
        int n = V;
        int[] dist = new int[n];
        for(int i=0; i<n; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        dist[src] = 0;

        int[] parent = new int[n];
        for(int i=0; i<n; i++){
            parent[i] = i;
        }

        djk(adj, src, dist, parent);

        int node = target;
        List<Integer> shortestPath = new ArrayList<>();
        while(parent[node]!=node){
            shortestPath.add(node);
            node = parent[node];
        }
        shortestPath.add(src);

        return shortestPath;
    }

    private void djk(List<List<List<Integer>>> adj, int src, int[] dist, int[] parent){

        PriorityQueue<Pair<Integer>> queue = new PriorityQueue<>((pairA, pairB) -> pairA.weight-pairB.weight);
        queue.add(new Pair(0, src));
        while(!queue.isEmpty()){
            Pair<Integer> pair = queue.poll();
            int vertex = pair.node;
            if(pair.weight > dist[vertex]){
                continue;
            }

            // int wt = pair.weight;

            for(List<Integer> neighbour : adj.get(vertex)){
                int edgeVertex = neighbour.get(0);
                int wt = neighbour.get(1);
                if(dist[edgeVertex] > dist[vertex] + wt){
                    dist[edgeVertex] = dist[vertex] + wt;
                    parent[edgeVertex] = vertex;
                    queue.add(new Pair(dist[edgeVertex], edgeVertex));
                }
            }
        }
    }

    private List<List<List<Integer>>> createAdjList(int V, int[][] edges){
        List<List<List<Integer>>> adjList = new ArrayList<>();

        for(int i=0; i<V; i++){
            adjList.add(new ArrayList<>());
        }

        for(int[] edge : edges){
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            adjList.get(u).add(List.of(v, weight));
        }

        return adjList;
    }
}