Problem Statement

Given a weighted, undirected graph of V vertices, numbered from 0 to V-1, 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 .

Given a source node S. Find the shortest distance of all the vertex from the source vertex S. Return a list of integers denoting shortest distance between each node and source vertex S. If a vertex is not reachable from source then its distance will be 10^9.

Dijkstra is a Single-Source-Shortest-Path algorithm, which means that it calculates shortest distance from one vertex to all the other vertices.

The node from where we want to find the shortest distance is known as the source node. The distance to source node is naturally going to be zero.

Examples

Example 1:

Input: V = 2,
       adj[] = [
                [[1, 9], [0, 9]]
               ]
      S = 0
Output: [0, 9]

Explanation:
The shortest distance from node 0 (source) to node 0 is 0 and the shortest distance from node 0 to node 1 is 6.

Example 2:

Input: V = 3
       adj = [
              [[1, 1], [2, 6]],
              [[2, 3], [0, 1]],
              [[1, 3], [0, 6]]
             ]
       S = 2
Output: [4, 3, 0]

Explanation:
For node 0 from node 2, the shortest path is 2->1->0 (distance = 4)
For node 1 from node 2, the shortest path is 2->1 (distnace = 3)
For node 2 from node 2, the shortest distance is 0

Example 3:

Input: V = 4
       adj = [
              [[1, 1], [3, 2]],
              [[0, 1], [2, 4]],
              [[1, 4], [3, 3]],
              [[0, 2], [2, 3]]
             ]
       S = 0

Output: [0, 1, 5, 2]

Explanation:
For node 0 from node 0, the shortest distance is 0
For node 1 from node 0, the shortest path is 0->1 (distnace = 1)
For node 2 from node 0, the shortest path is either of 0->1->2 or 0->3->2 both have distance of 5
For node 3 from node 0, the shortest path is 0->3 (distance = 2)

Different Approaches

1️⃣ Using Min-Heap

Dijkstra's Algorithm

It is used in connected graphs (undirected as well as directed) whenever it is required to find out the shortest distance from the source node to every other node.

Conditions for Dijkstra's Algorithm to work?

The graph must not have any non-negative edge weights.

Algorithm

• Set the distance to the starting node as 0 and to all other nodes as infinity(a big value). Add all nodes to an unvisited set. Begin with the starting node.
• Perform Edge Relaxation i.e., for each unvisited neighbor of the current node, calculate the tentative distance from the start node. If this tentative distance is less than the known distance, update it.
• Mark the current node as visited once all its neighbors have been evaluated. It won't be checked again. Choose the unvisited node with the smallest tentative distance as the new current node.
• Repeat steps 2-3 until all the nodes are visited. Once all nodes are visited, the shortest path to all the nodes is now known.

Implementation:

To implement the Dijkstra's Algorithm, a minimum heap data structure (Priority Queue) can be used. The priority queue will store the pair {dist, node} storing the tentative distance required to reach the node from the source node. If this distance is found to be smaller than the known distance, we update the distance to reach node and push to newly found pair of {dist, node} in the priority queue.

Significance of using a Min-Heap data structure:

Storing the pair {dist, node} in min-heap ensures that out of all the pairs, the node with the minimum distance (from source node) is taken into consideration first. This helps the algorithm to explore the shortest path first improving efficiency.

Approach:

1. Use a priority queue to process nodes by their shortest known distance.
2. Initialize an array to store shortest distances, with the source node set to 0 and all others to infinity.
3. Add the source node to the priority queue with a distance of 0.
4. Extract the node with the smallest distance from the queue and perform edge relaxation (update the distances to its neighbors if a shorter path is found). Add the updated neighbors back to the queue.
5. The distance array contains the shortest distances from the source to all node.

Code:

class Solution {
public:
    vector<int> dijkstra(int V, vector<vector<int>> adj[], int S) {
        // Min-heap priority queue to always process the vertex with the smallest known distance.
        // The queue stores pairs of (distance, vertex).
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        // Initialize the distance vector with a large value (infinity equivalent).
        // Set the source vertex S's distance to 0.
        vector<int> distance(V, 1e9);
        distance[S] = 0;
        
        // Push the source vertex into the priority queue.
        pq.push({0, S});
        
        // Continue processing until the priority queue is empty.
        while (!pq.empty()) {
            // Extract the vertex with the minimum distance from the queue.
            auto front = pq.top();
            pq.pop();
            
            // Current known shortest distance for the extracted vertex.
            int current_distance = front.first;
            // The vertex being processed.
            int node = front.second;
            
            // Explore all adjacent edges from the current vertex.
            // Each edge is represented as a vector where:
            // edge[0] is the neighboring vertex and edge[1] is the weight of the edge.
            for (auto edge : adj[node]) {
                int neighbor = edge[0]; // Adjacent vertex.
                int weight = edge[1];   // Edge weight.
                
                // If the current path offers a shorter route to the neighbor, update the distance.
                if (current_distance + weight < distance[neighbor]) {
                    distance[neighbor] = current_distance + weight;
                    // Push the updated distance and neighbor into the priority queue.
                    pq.push({distance[neighbor], neighbor});
                }
            }
        }
        
        // Return the final computed shortest distances from source S to all vertices.
        return distance;
    }
};

Complexity Analysis:

• Time Complexity: O((V+E)*logV) (where V and E represent the number of nodes and edges of the graph)
  • Each node is processed once in the priority queue and deletion and insertion operation takes O(logV) time making it overall O(V*logV) in the worst case.
  • For each vertex, all its edges are relaxed. This operation involves updating the priority queue, which takes O(logV) making it overall O(E*logV) for E edges in the worst case.
• Space Complexity: O(V)
  • The priority queue will store distances to all nodes in worst case leading to O(V) space.
  • The distance array takes O(V) space.

2️⃣ Using Set

Dijkstra's Algorithm is used in connected graphs (undirected as well as directed) whenever it is required to find out the shortest distance from the source node to every other node.

Conditions for Dijkstra's Algorithm to work?

The graph must not have any non-negative edge weights.

Algorithm:

1. Set the distance to the starting node as 0 and to all other nodes as infinity. Add all nodes to an unvisited set. Begin with the starting node.
2. Perform Edge Relaxation i.e., for each unvisited neighbor of the current node, calculate the tentative distance from the start node. If this tentative distance is less than the known distance, update it.
3. Mark the current node as visited once all its neighbors have been evaluated. It won't be checked again. Choose the unvisited node with the smallest tentative distance as the new current node.
4. Repeat steps 2-3 untill all the nodes are visited. Once all nodes are visited, the shortest path to all the nodes is now known.

Implementation: Using Set

To implement the Dijkstra's Algorithm, a set data structure can be used. The set will store the pair {dist, node} storing the tentative distance required to reach the node from the source node. If this distance is found to be smaller than the known distance, we update the distance to reach node and insert the newly found pair of {dist, node} in the set.

Significance of using a Set data structure:

• Storing the pair {dist, node} in set ensures that out of all the pairs, the node with the minimum distance (from source node) is taken into consideration first. This helps the algorithm to explore the shortest path first improving efficiency.
• Another added advantage in the set is that it can perform deletion operations on pairs that are found to be unfruitful saving some iterations.

Approach:

1. Create a distance array initialized to infinity (1e9), except for the source vertex which is set to 0.
2. Use a set to store pairs of (distance, node), starting with the source node with a distance of 0.
3. Continuously extract the node with the smallest distance from the set until the set is empty.
4. For the current node, iterate through all its adjacent nodes. Calculate the tentative distance to each neighbor. If this distance is smaller than the known distance, update the distance and adjust the set.
5. After processing all nodes, return the distance array containing the shortest distances from the source to all nodes.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the shortest distance of all 
    the vertices from the source vertex S. */
    vector <int> dijkstra(int V, vector<vector<int>> adj[], 
                         int S) {
                             
        // Set to store {dist, node}
        set <pair<int,int>> st;
        
        // Distance array 
        vector<int> dist(V, 1e9);
        
        // Distance of source node from itself is 0
        dist[S] = 0;
        
        // Adding the source node to set
        st.insert({0, S});
        
        // Until the set is empty
        while(!st.empty()) {
            
            // Get the distance
            int dis = st.begin()->first;
            
            // Get the node
            int node = st.begin()->second;
            st.erase(st.begin());
            
            // Traverse all its neighbors
            for(auto it : adj[node]) {
                int adjNode = it[0]; // node
                int edgeWt = it[1]; // edge weight
                
                /* If the tentative distance to 
                reach adjacent node is smaller 
                than the known distance */
                if(dis + edgeWt < dist[adjNode]) {
                    
                    /* If another longer known distance 
                    is found, erase it from the set */
                    if(dist[adjNode] != 1e9) 
                        st.erase({dist[adjNode] , adjNode});
                    
                    // Update the known distance
                    dist[adjNode] = dis + edgeWt;
                    
                    // Add the new pair to the set
                    st.insert({dist[adjNode] , adjNode});
                }
            }
        }
        
        // Return the result
        return dist;
    }
};

int main() {
    
    int V = 2, S = 0;
    vector<vector<int>> adj[V] = 
    {
        {{1, 9}}, 
        {{0, 9}}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the shortest distance 
    of each node from the source node */
    vector<int> ans = sol.dijkstra(V, adj, S);
    
    // Output
    cout << "The shortest distance of nodes from the source node is: ";
    for(int i=0; i < V; i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O((V+E)*logV) (where V and E represent the number of nodes and edges of the graph)
  • Each node is processed once in the set and deletion and insertion operation takes O(logV) time making it overall O(V*logV) in the worst case.
  • For each node, all its edges are relaxed. This operation involves updating the set, which takes O(logV) making it overall O(E*logV) for E edges in the worst case.
• Space Complexity: O(V)
  • The set will store distances to all nodes in worst case leading to O(V) space.
  • The distance array takes O(V) space.