Please Share dijkstra's algorithm questions

when you pop the queue don’t explore that node if it’s current distance is less than the popped distance from the queue.

As a side note, these lines inside main are useless:

lli dist[v+1]={0};
bool flags[v+1]={0};
1 Like

I don’t understand what i should change ? can u please edit my code .

while(!pq.empty()){
        
        pii mpair = pq.top();
        
        lli u  = mpair.S;
        
        pq.pop();
        
        
        for(auto xt : adj[u]){
            
            lli v = xt.F;
            
            lli weight = xt.S;
            
            if(dist[v] > (dist[u] + weight) )
            {
               dist[v] = dist[u] + weight;

               pq.push(make_pair(dist[v] , v));
            }
            
        }
        
    }

Just one line added…

Code
while(!pq.empty()){
        pii mpair = pq.top();
        lli u  = mpair.S;
        pq.pop();
        if (mpair.first > dist[u]) continue;
        for(auto xt : adj[u]){
            lli v = xt.F;
            lli weight = xt.S;
            if(dist[v] > (dist[u] + weight) )
            {
               dist[v] = dist[u] + weight;
               pq.push(make_pair(dist[v] , v));
            }
        } 
    }
1 Like

Yeah before u answer i changed and AC…thanks :slight_smile:

Can u please give me an simple example where I unnecessarily explore the nodes , bcz I don’t understand how a single if made program AC , Please give an example so I can understand more better.

build yourself a complete graph (every node connected with every node) with random weights and do it on paper

1 Like

Thanks , Now I understand , same pair of node with the different cost is added in min heap so when higher cost pair is poped then there is no meaning for that node as already by smaller cost we explored its adjacent, Thanks man .

1 Like

Surprised to see every other Dijkstra implementation online misses this. :no_mouth:.

yes and it increases complexity too much , one of problem on leet code passes with 300 ms but when I put if condition ( as caree said) , then it passed in 200 ms only.

1 Like

As said here, “…this check is important, otherwise the complexity can increase up to O(nm)”.

2 Likes

A bit late, but I always liked this one:

2 Likes

Will try , btw u come after very long time…

1 Like

It’s never too late! :relieved:. Keep `em coming.

3 Likes

yeah lol