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!*

Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | Um_nik | 3535 |

4 | 300iq | 3317 |

5 | ecnerwala | 3294 |

6 | maroonrk | 3268 |

7 | TLE | 3223 |

8 | scott_wu | 3209 |

9 | WZYYN | 3180 |

10 | boboniu | 3174 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 197 |

2 | antontrygubO_o | 185 |

3 | pikmike | 183 |

4 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 173 |

7 | SecondThread | 167 |

8 | Um_nik | 164 |

9 | Monogon | 163 |

10 | McDic | 162 |

Hello folks,

I have a small doubt regarding `Dijkstra Algorithm`

*The highlighted part*,

*What's the main use of the line?*

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/11/2020 21:45:37 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

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 50000and 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.Hey,

Obviously,

`cur_d`

will be equal to`d[v]`

, right? because on the line`38`

, we are pushing`( -d[to], to )`

Correct me please.