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
Auto comment: topic has been updated by Saksham_Sahgal (previous revision, new revision, compare).
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 wrote a Recursive Brute solution , it gives the correct ans by trying all possible combination of paths , but for delivery locations more than 8 it takes around 10 seconds of calculation , is there any near optimal clustering algorithm that gives a desant answer , basically what i want is —
A clustering algorithm that -
1>takes a vector containing all delivery location vertices as an input
2>divide that vector of delivery location vertices into M no of groups such that each element of the vector (a delivery vertex) belongs to exactly one group. (Considering M <= x)
We are dividing that delivery location vertices into groups so we can give each driver a group of delivery locations.
example -
for a this graph —
the most optimal ways are —
for minimal time -
Minimum time possible — 53 ( Clustering for this method is shown above )
Mini time path traversed -
driver 1 -> 1 6 9 6 3 22
driver 2 -> 1 5 12 13 8 7
driver 3 -> 1 18 1 20
for minimum total distance travelled -
Minimum distance possible — 112
Mini distance traversal -
driver 1 -> 1 5 12 13 10 9 10 7 3 22
driver 2 -> 1 18
driver 3 -> 1 20