Posts Dijkstra Algorithm (geeksforgeeks - SDE Sheet)
Post
Cancel

Dijkstra Algorithm (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given a weighted, undirected and connected graph of V vertices and an adjacency list adj where adj[i] is a list of lists containing two integers where the first integer of each list j denotes there is edge between i and j , second integers corresponds to the weight of that edge . You are given the source vertex S and You to Find the shortest distance of all the vertex’s from the source vertex S. You have to return a list of integers denoting shortest distance between each node and Source vertex S.

geeksforgeeks

SOLUTION

  • Create a distance array to store the shortest distance from the source to each vertex, initializing all values to infinity (Integer.MAX_VALUE), except the source vertex which is set to 0.
  • Use a Priority Queue to process vertices based on their current shortest distance (smallest distance first).

  • Add the source vertex to the priority queue with a distance of 0.

  • While the priority queue is not empty:

    • Remove the vertex with the smallest distance from the queue.
    • For each neighbor of this vertex:
      • Check if going through this vertex offers a shorter path to the neighbor.
      • If it does, update the neighbor’s distance and add the neighbor to the queue with the new distance.
  • Continue this process until all vertices have been processed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {

    static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S) {

        // Array to store the shortest distances from source to each vertex
        int[] distance = new int[V];

        // init: infinity (MAX_VALUE) to represent they are unreachable initially
        Arrays.fill(distance, Integer.MAX_VALUE);

        // Distance from source to itself is always 0
        distance[S] = 0;

        // Priority queue to process nodes by their current shortest distance (min-heap)
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.distance - b.distance);

        // Add the source node to the priority queue with distance 0
        pq.add(new Node(S, 0));

        // While there are nodes in the priority queue to process
        while (!pq.isEmpty()) {

            // Extract the node with the smallest distance (the most promising node)
            Node node = pq.poll();

            // Current vertex (u) and its distance from the source
            int u = node.vertex;
            int d = node.distance;

            // Explore all neighbors of vertex u
            for (int i = 0; i < adj.get(u).size(); i++) {

                // Get the neighbor (adjacent vertex and the weight of the edge)
                ArrayList<Integer> neighbor = adj.get(u).get(i);

                int neighborVertex = neighbor.get(0);
                int neighborWeight = neighbor.get(1);

                // If a shorter path to neighborVertex is found, update it
                if (d + neighborWeight < distance[neighborVertex]) {

                    // Update the shortest distance to the neighborVertex
                    distance[neighborVertex] = d + neighborWeight;

                    // Add the neighbor to the priority queue with the updated distance
                    pq.add(new Node(neighborVertex, distance[neighborVertex]));

                }
            }
        }

        return distance;
    }
}

// Node class to represent a vertex and its distance
class Node {

    int vertex;
    int distance;

    Node(int vertex, int distance) {
        this.vertex = vertex;
        this.distance = distance;
    }
}
This post is licensed under CC BY 4.0 by the author.