dark___horse's blog

By dark___horse, 5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

give more details about what type of graph is it. 1. is it directed or undirected? 2. is it weighted or unweighted?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dark___horse (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone? please.

»
5 months 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)

»
5 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I had some idea but it doesn't work

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dark___horse (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dark___horse (previous revision, new revision, compare).