Implementation details of dijkstras

#1

Well as described in the video inside the while loop there will be repeated unnecessary calling of those elements as well whose shortest paths have been decided shouldnt we maintain something which tells us that this node has already been decided upon and we dont need to relax that node anymore

#2

no there wont be any reption call in dijkstra …

#3

void Dijkstra(int r, int n)
{
priority_queue<pii, vector <pii >, greater<pii> > Q;
dis.assign(n+1,1e18);
dis[r] = 0;
Q.push({0,r});

 while(!Q.empty())
 {
    int u = Q.top().second;
    Q.pop();
    for(auto &c : v[u])
    {
        int x = c.first;
        int w = c.second;
        if(dis[x] > dis[u]+w)
        {
            dis[x] = dis[u]+w;
            Q.push({dis[x],x});
        }
    }
 }

}

#4

for the code implemented in the video I guess there will be repeated calls for those elements whose shortest distance have been finalized …
but they will fail the relaxing condition and therefore wont affect the result?

#5

this code is fine :+1:

#6

bdw pii is pair in my code. dis is vector … you have got the logic…now you can use this code always… save it as snippet…

1 Like
#7

yes I got it btw I have your #defines also stored up :sweat_smile:

#8

:smiley: thats great…