### call_me_hopeless28's blog

By call_me_hopeless28, history, 10 months ago, ,

#### Hello everyone

I was trying to solve this problem. I have tried to solve this problem about 18 hours but I failed.I think it can be solved using k-th shortest path algorithm but I can't find an understandable article on k-th shortest path algorithm.Can anyone please explain the k-th shortest path finding algorithm. I know the Dijstra's algorithm. Also, if it can be solved using other algorithm then please help me to know the algorithm.

•
• +9
•

 » 10 months ago, # |   +13 You have to find second shortest distance in a graph from node 1 to node N.Hint: Store first and second shortest distances for every node from node 1. Use Dijkstra's algorithm now. If you haven't visited a node, the distance will be shortest distance. If you have visited it once, the distance will be second shortest. For further visits, ignore the distance.
•  » » 10 months ago, # ^ |   0 Thanks for your hint I will try and get back if I fail again.
 » 10 months ago, # |   +3 When you think about a more general problem, try to ask yourself "is it solvable?". In the case of finding the k-th sortest path, it's probably not solvable because you could probably use it to find a Hamiltonian path (https://en.wikipedia.org/wiki/Hamiltonian_path) which is a NP-complete problem. That being said, praran26's hint is the right direction to the second shortest distance.
•  » » 10 months ago, # ^ |   0 Thank you for your advice. I am trying to solve using prraran26's hint