Блог пользователя i_am_eating_wa_and_tle

Автор i_am_eating_wa_and_tle, история, 7 лет назад, По-английски

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
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +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.

»
7 лет назад, # |
  Проголосовать: нравится +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.