I have started learning dijkstra algorithm but i can not solve any problem on any ojs. I don't know how to find second shortest path or these kinda problem . I just can figure out shortest path. How can i be an expert on dijkstra algo?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3443 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
2 | atcoder_official | 163 |
4 | maomao90 | 162 |
5 | adamant | 158 |
5 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | djm03178 | 154 |
8 | TheScrasse | 154 |
10 | Dominater069 | 153 |
I have started learning dijkstra algorithm but i can not solve any problem on any ojs. I don't know how to find second shortest path or these kinda problem . I just can figure out shortest path. How can i be an expert on dijkstra algo?
Name |
---|
Dijkstra finds paths in non-decreasing order of cost. For regular shortest path problems, you do not continue searching paths that aren't the shortest for that vertex, however in second-shortest path you need to keep a counter for how many times a vertex has been dequeued from the priority queue / heap, and continue the search if it's the shortest or second-shortest path.
Do you have the code link?
https://lightoj.com/submission/2300476
Edit: I'm not sure whether you can view this submission, so:
Link to problem: https://lightoj.com/problem/not-the-best
Code (Rust): https://www.toptal.com/developers/hastebin/ifukayaqov.rust
Codeforces graphs and shortest paths tags (Editorial if you can't solve them)
Cses graph problems
Book
get brain (and use it)
Try to understand and challenge each step of algorithm, try to come up with counter examples. Soon you will find out why it actually works and how to extend it to other problems. Post here if you get stuck.
Might as well use the USACO guide. Under the gold section in the Shortest Path with nonnegative weights, there are nice problems from various OIs and OJs with most of them having an internal solution