i_love_snz28's blog

By i_love_snz28, history, 7 days 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  

»
7 days 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.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your hint I will try and get back if I fail again.

»
7 days 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 (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.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your advice. I am trying to solve using prraran26's hint