Dikstra's Algorithm

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 .

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

The structure of adjacency list is as follows :-

For Example : adj = { {{1, 1}, {2, 6}} , {{2, 3}, {0, 1}} , {{1, 3}, {0, 6}} }

Here adj[i] contains a list which contains all the nodes which are connected to the ith vertex. Here **adj[0] = ** { {1, 1}, {2, 6}} means there are **two **nodes conneced to the 0th node, node 1 with an edge weight of 1 and **node 2 with an edge weight of 6 **and similarly for other vertices.

Example 1:

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

The source vertex is 0. Hence, the shortest
distance of node 0 is 0 and the shortest
distance from node 1 is 9.

Example 2:

Input:
V = 3, E = 3
adj = {{{1, 1}, {2, 6}}, {{2, 3}, {0, 1}}, {{1, 3}, {0, 6}}}
S = 2
Output:
4 3 0
Explanation:

For nodes 2 to 0, we can follow the path-
2-1-0. This has a distance of 1+3 = 4,
whereas the path 2-0 has a distance of 6. So,
the Shortest path from 2 to 0 is 4.
The shortest distance from 0 to 1 is 1 .

 vector <int> dijkstra(int V, vector<vector<int>> adj[], int S)
    {
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
        pq.push({0,S});
        vector<int> dist(V,1e9);
        dist[S]=0;
        while(!pq.empty()){
            pair<int,int> temp=pq.top();
            pq.pop();
            int node=temp.second;
            int dis=temp.first;
            for(auto it:adj[node]){
                int edge_weight=it[1];
                int next_node=it[0];
                if(dist[next_node]>edge_weight+dis){
                    dist[next_node]=edge_weight+dis;
                    pq.push({edge_weight+dis,next_node});
                }
            }
        }
        return dist;
    }