0

When we are writing dijkstra algorithm with priority queue why we are not check about the visited node?

while (!pq.empty())
    {
        
        int u = pq.top().second;
        pq.pop();
 
        // Get all adjacent of u.
        for (auto x : adj[u])
        {
            int v = x.first;
            int weight = x.second;
 
            if (dist[v] > dist[u] + weight)
            {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
Khushi Patel
  • 1
  • 1
  • We always process the next node with least distance at a given stage greedily. We never process that node again. What is your doubt? – Shridhar R Kulkarni Jun 21 '22 at 03:59
  • That pseudocode assumes that you are using the *decrease-key* feature of the priority queue. When you push a pair (and the vertex is already in the queue), the existing entry is updated with the new (smaller) distance. – user3386109 Jun 21 '22 at 06:05
  • @ShridharRKulkarni Dikjstra is greedy algorithm so once it got shortest path it will not see that again and that's why its not work in -ve edges as per this answer : https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges but when we write using priority queue it will work for -ve edge so my doubt is that it is write way of doing or in queue also we have to check for visited – Khushi Patel Jun 22 '22 at 05:34
  • @KhushiPatel Dijkstra's does not work with negative weight edges, period. When the graph contains negative edges, use Bellman-Ford. See for example [the third paragraph here](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Related_problems_and_algorithms). – user3386109 Jun 22 '22 at 17:20
  • @ShridharRKulkarni Can you please give me one example of -ve edges that not work on this code? – Khushi Patel Jun 24 '22 at 05:04

1 Answers1

0

It does check the previous value of the node in dist[v], which I assume stores the current best distance from the root (or u) to node v. If a new path is found to v which is shorter than the previous shortest one, it is reinserted into the priority queue because it may now provide shorter paths to other nodes. If this new distance to v is longer than the previous, then it is left alone. This is why there is no else in the implementation.

tk744
  • 43
  • 6