i_am_eating_wa_and_tle's blog

Help needed on finding the k-th shortest path algorithm ???
By i_am_eating_wa_and_tle, history, 7 years 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

Comments Comments (2)
| Write comment?
»
7 years 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.

→ Reply
»
7 years 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.

→ Reply