call_me_hopeless28's blog

By call_me_hopeless28, history, 6 months ago, In English,

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.

  • Vote: I like it  
  • +9
  • Vote: I do not like it  

6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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 ( which is a NP-complete problem. That being said, praran26's hint is the right direction to the second shortest distance.