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!# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
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!Name |
---|
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.
Ok thanks ,
So, does this code work fine instead of using that line ?
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"
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 doif (visited[u]) continue;
right before your for loop in your dijkstra version, and that will do the trick.