problem implementing Dijkstra's single source shortest path algorithm



I am trying to implement Dijkstra’s single source shortest path algorithm using priority queue data structure and I got stuck at some point.

I am using adjacency list representation of graph, I want to retrieve weight of edge(x,y) how to do it efficiently.


using namespace std;
#define INF INT_MAX //Infinity

    const int sz=10001; //Maximum possible number of vertices. Preallocating space for DataStructures accordingly
    vector<pair<int,int> > a[sz]; //Adjacency list
    int dis[sz]; //Stores shortest distance
    bool vis[sz]={0}; //Determines whether the node has been visited or not
    void Dijkstra(int source, int n) //Algorithm for SSSP
        for(int i=0;i<sz;i++) //Set initial distances to Infinity
        //Custom Comparator for Determining priority for priority queue (shortest edge comes first)
        class prioritize{public: bool operator ()(pair<int, int>&p1 ,pair<int, int>&p2){return p1.second>p2.second;}};
        priority_queue<pair<int,int> ,vector<pair<int,int> >, prioritize> pq; //Priority queue to store vertex,weight pairs
        pq.push(make_pair(source,dis[source]=0)); //Pushing the source with distance from itself as 0
            pair<int, int>; //Current vertex. The shortest distance for this has been found
            int cv=curr.first,cw=curr.second; //'cw' the final shortest distance for this vertex
            if(vis[cv]) //If the vertex is already visited, no point in exploring adjacent vertices
            for(int i=0;i<a[cv].size();i++) //Iterating through all adjacent vertices
                if(!vis[a[cv]*.first] && a[cv]*.second+cw<dis[a[cv]*.first]) //If this node is not visited and the current parent node distance+distance from there to this node is shorted than the initial distace set to this node, update it
                    pq.push(make_pair(a[cv]*.first,(dis[a[cv]*.first]=a[cv]*.second+cw))); //Set the new distance and add to priority queue
    int main() //Driver Function for Dijkstra SSSP
        int n,m,x,y,w;//Number of vertices and edges
        //cout<<"Enter number of vertices and edges in the graph

for(int i=0;i<m;i++) //Building Graph
cin>>x>>y>>w; //Vertex1, Vertex2, weight of edge
//cout<<"Enter source for Dijkstra’s SSSP algorithm
int source;
Dijkstra(source,n);//SSSP from source (Also passing number of vertices as parameter)
cout<<"Source is: “<<source<<”. The shortest distance to every other vertex from here is:
for(int i=1;i<=n;i++)//Printing final shortest distances from source
cout<<“Vertex: “<<i<<” , Distance: “;
dis*!=INF? cout<<dis*<<”
" : cout<<”-1
return 0;

[Here]( is the code in action . If you have any queries ask in the comments !



I am coding in java, I am not familiar with STL so I am not getting this code.


I tried explaining the code here with usage of STL specifically. Take a look .



why priority queue is declared like this
priority_queue<pair<int,int> ,vector<pair<int,int> >pq;

why does it have vector in it.


There are three parameters required here .

  1. type of the elements (pair<int,int>)
  2. Type of the internal underlying container object where the elements are stored.(that’s what vector is used here for )
  3. A binary predicate that takes two elements (of type T) as arguments and returns a bool.(this is optional, by default - max priority_queue )