### Saksham_Sahgal's blog

By Saksham_Sahgal, history, 10 days ago,

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)

• +13

 » 10 days ago, # |   0 Seems like a pretty standard shortest path problem, where are you stuck at? what have you tried so far?
•  » » 10 days ago, # ^ |   +11 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 .
•  » » » 10 days ago, # ^ |   0 Oh, I didn't understand the problem correctly then, refer to algoishard 's comment
 » 10 days ago, # |   0 Auto comment: topic has been updated by Saksham_Sahgal (previous revision, new revision, compare).
 » 10 days ago, # | ← Rev. 2 →   +25 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).
•  » » 7 days ago, # ^ | ← Rev. 2 →   +12 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.
•  » » » 6 days ago, # ^ |   0 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.
•  » » » » 3 days ago, # ^ | ← Rev. 3 →   0 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 input2>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 — delivery locations marked as green source marked as black we are considering 3 drivers originating from the sources 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 22driver 2 -> 1 5 12 13 8 7driver 3 -> 1 18 1 20for minimum total distance travelled - Minimum distance possible — 112Mini distance traversal -driver 1 -> 1 5 12 13 10 9 10 7 3 22driver 2 -> 1 18driver 3 -> 1 20