Mo_Huzaifa's blog

How can i learn dijkstra algorithm properly as a newbie ?
By Mo_Huzaifa, history, 2 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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

Cses graph problems

Book

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

get brain (and use it)

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like 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.

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

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

→ Reply