kittyK's blog

Second Shortest Path
By kittyK, history, 4 years ago, In English

Anyone please help me with this problem

Here, you are asked to find second shortest path.

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

what complexity you need? what limit for n,m?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Find shortest path from s to t using Dijkstra's algo. but, you should also store the value of the second best distance. So before overwriting smallestDistance, also store its discarded value. Do this only when the node in consideration is the target node. At the end, you would have second shortest distance.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

now try this problem:P https://cses.fi/problemset/task/1196 the idea for the 2 case, as Ebiarat is just maintaining for information, here the distance of the second best path from s to t

→ Reply