Блог пользователя Mo_Huzaifa

Автор Mo_Huzaifa, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

Codeforces graphs and shortest paths tags (Editorial if you can't solve them)

Cses graph problems

Book

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

get brain (and use it)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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