Given a weighted undirected graph , a source vertex(s) and x distinct vertices as Delivery Location (d1 , d2 , d3 .. dx) assuming that each rider travels at 1m/s what is the min time required to complete all the deliveries if you have M drivers originating from the source simultainously , and also the path followed by them.
( it is guarented that reaching all delivery locations from the source vertex is possible )
input format -
n m s M //n vertices , m edges , s is the source vertex , M no of drivers
v11 v12 w1 //vertices connected with weight w
v21 v22 w2
..
vm1 vm2 wm
x // no of delivery locations 1<= x < n
d1 , d2 , d3 , d4 .... dx //delivery vertices (d[i] != s for all 1 <= i <= x)
output format - (M+1 lines first line should contain the min time required and all others M lines should include paths followed by drivers from 1 to M)
t //min time to complete all deliveries
1->3->5 // path followed by first delivery guy
1->2->1->5 // path followed by second delivery guy
1-> path followed by third delivery guy (it may be possible that this delivery person didn't moved so his path finished at source only)
(all paths should start from source only)
Seems like a pretty standard shortest path problem, where are you stuck at? what have you tried so far?
the problem is that there are multiple drivers , Eg let the source be 1 and let's say the weights are arranged in such a way, that to do the deliveries in min time , first guy delivers to 7 and 14 while simultaneously second guy delivers to 3 and 6 .
Oh, I didn't understand the problem correctly then, refer to algoishard 's comment
It's unclear whether after the delivery the delivery person has to go back to the source. If this is not the case, this problem is NP-hard as TSP can be reduced to this problem with M = 1 and x = n.
And, even if it is the case that the delivery person has to go back to the source after every delivery, the problem is still NP-hard because subset sum problem can be reduced to this problem with M = 2 and x = n (unless edge weight is polynomial in n).
No the delivery person doesn't have to go back to source after every delivery , the goal is to complete all deliveries in one go.
So we need more info on the constraints. Like I have mentioned, this problem is NP-hard so you shouldn't expect to come up with any polynomial time algorithm.
I made a visual Simulator version of this problem — Link
you can check it out if you are interested :>