dark___horse's blog

By dark___horse, 3 years ago, In English

Given a directed and weighted graph without negative edges in it with n nodes, a source and a destination, what is the shortest path from source to the destination when we are allowed to visit at most k nodes?

Can someone suggest better ways I can use to solve this problem?

link to the problem

my accepted solution to the problem

Thanks in advance!!

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

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think if k is small you can do Bellman Ford alghoritm except you do first loop k-1 times (n-1 in original)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be nice if you could give us a link to the problem.