vkditya0997's blog

doubt regarding Dijkstra Algorithm

By vkditya0997, history, 9 years ago, In English

Hello folks,

I have a small doubt regarding Dijkstra Algorithm



The highlighted part,

    What's the main use of the line?

Thanks in Advance and Merry Christmas!
  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Same node can be pushed into queue more than once, those same nodes in queue have distinct costs.It is enough to update queue just with the smallest cost value for a node. That "if" make loops work just once for each node.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok thanks ,
    So, does this code work fine instead of using that line ?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It will work, but you'll have a lot of edge visiting because some input can make your code run in O(n^2 log n). For example, if the edge list looks this (n = 10^5, format "u v w"

      1 2 1
1 3 1
1 4 1
1 5 1
...
1 49999 1
2 50000 2
3 50000 3
4 50000 4
...
49998 50000 49998
49999 50000 49999
50000 50001 1
50000 50002 1
50000 50003 1
...
50000 99999 1
50000 10000 1

      What's happening here is every node in the range [2: 49999] has an edge from node 1 with a uniform weight of 1. All if them will be visited normally.

      However, once the second batch will be processed, all edges from [2: 49999] will converge to node 50000. Note that d[50000] will be updated 49998 times before visiting node 50000 and thus node 50000 will be pushed that number of times in the priority queue before it will be officially visited.

      Here comes the hack. Since you are not checking (and breaking) if the visited state has a different min distance, come third wave of edges from 50000 to [50001: 100000] you will end up adding 50000 edges 49998 times. Your algorithm does not fail but it's now O(n^2 log n) instead of O(n log n).

      That's just one edge case. The one line if (cur_d > d[v]) continue; ensures you visit every node once. You can also do if (visited[u]) continue; right before your for loop in your dijkstra version, and that will do the trick.

      → Reply