Shortest Path Algorithm - Dijkstra algorithm

SINGLE SOURCE ALGORITHM

Given a weighted, undirected and connected graph where you have given adjacency list adj. You have to find the shortest distance of all the vertices from the source vertex src, and return a list of integers denoting the shortest distance between each node and source vertex src.

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

Practice Link

Note#

Cannot have negative edge cycle. -> FAILS

Why?

The problem with negative weights arises from the fact that Dijkstra’s algorithm assumes that once a node is added to the set of visited nodes, its distance is finalized and will not change. However, in the presence of negative weights, this assumption can lead to incorrect results.

Algorithm#

• We start by initializing an adjacency list which will store all the adjacent nodes for a particular node along with the weights associated with them.
• Then, as a part of the initial configuration, we define a dist array to store the updated shortest distances for each node, a priority queue for storing the distance-node pairs, and a source node.
• In addition to this, we also declare a ‘parent’ array which would store the parent node for each node and will update itself to a different parent if a shorter path from a node is found at some point in time.
• At the start, all nodes’ parents have been set to the nodes themselves to indicate that the traversal has not yet been started.
• For every node at the top of the queue, we pop the element out and look out for its adjacent nodes. If the current reachable distance is better than the previous distance (dis + edW < dist[adjNode]), indicated by the distance array, we update the distance and push it into the queue.
• A node with a lower distance would be at the top of the priority queue as opposed to a node with a higher distance because we are using a min-heap.
• In addition to the previous step, we will also update the parent array to the node from where the current node came while traversing.
• By following step 5 repeatedly until our queue becomes empty, we would get the minimum distance from the source node to all other nodes and also our parent array would be updated according to the shortest path.
• Now, we run a loop starting from the destination node storing the node’s parent and then moving to the parent again (backtrack) till the parent[node] becomes equal to the node itself.
• At last, we reverse the array in which the path is being stored as the path is in reverse order. Finally, we return the ‘path’ array.

Data structures Used#

• Priority Queue (min-heap): store path-> node
• dist array: to store distance from source
• parent array: to store the path -> can backtrack and find path until parent[u] != u

Implementation#

typedef pair<int,int> pii;

vector<int> dijkstra(vector<vector<pair<int, int>>> &adj, int src) {
        
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        
        vector<int> dist(adj.size(), INT_MAX);
        
        pq.push({0,src});
        dist[src] = 0;
        
        while(!pq.empty())
        {
            int u = pq.top().second;
            int wt = pq.top().first;
            pq.pop();
            

            for(auto it: adj[u])
            {
                int v = it.first;
                int dis = it.second;
                
                if(dist[v] > wt + dis )
                {
                    dist[v] = wt+dis;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
        
    }

Time Complexity: O( (E+V) log(V) ) (for Dijkstra’s Algorithm) Where E = Number of edges and V = Number of Nodes.

Space Complexity: O( |E| + |V| ) (for priority queue and dist array) + O( |V| ) (for storing the final path) Where E = Number of edges and V = Number of Nodes.

If path is needed#

vector<int> dijkstra(int V, vector<vector<int>> adj[], int S, vector<int> &parent) {
    priority_queue<pii,vector<pii>, greater<pii>> pq;
    vector<int> dist(V, 1e9);

    pq.push({0,S});
    dist[S]=0;
    parent[S]=-1;

    while(!pq.empty()){
        auto [wt, node] = pq.top();
        pq.pop();

        for(auto it: adj[node]){
            int adjNode = it[0];
            int edgeWt = it[1];

            if(dist[adjNode] > wt + edgeWt){
                dist[adjNode] = wt + edgeWt;
                parent[adjNode] = node;
                pq.push({dist[adjNode], adjNode});
            }
        }
    }
    return dist;
}

vector<int> getPath(vector<int> parent, int S, int D){
    vector<int> path;
    if(parent[D]==-1 && S!=D)
        return path;

    for(int curr=D;curr!=-1;curr=parent[curr]){
        path.push_back(curr);
    }

    reverse(path.begin(),path.end());
    return path;
}

Complexity Justification#

1. Each vertex is extracted from heap at most once (the final shortest distance)

   • V pop operations
   • Each pop: O(log V) (heap size ≤ V)
   • Total pop cost = O(V log V)

2. Each edge can lead to at most one relaxation and push

   • When we relax an edge (u → v), we push (dist[v], v) into the heap.
   • E push operations
   • Each push: O(log V) (heap insertion)
   • Total push cost = O(E log V)