### Saksham_Sahgal's blog

By Saksham_Sahgal, history, 3 months 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)

• +21

 » 3 months ago, # |   0 Seems like a pretty standard shortest path problem, where are you stuck at? what have you tried so far?
•  » » 3 months 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 .
•  » » » 3 months ago, # ^ |   0 Oh, I didn't understand the problem correctly then, refer to algoishard 's comment
 » 3 months ago, # |   0 Auto comment: topic has been updated by Saksham_Sahgal (previous revision, new revision, compare).
 » 3 months 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).
•  » » 3 months 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.
•  » » » 3 months 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 months 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
•  » » » » 7 weeks ago, # ^ |   +8 I made a visual Simulator version of this problem — Linkyou can check it out if you are interested :>
 » 7 weeks ago, # |   0 Source of the problem statement? Was it asked in interview?Thanks in advance :)
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 No it wasn't asked in an interview , this problem just popped into my mind when i was thinking of project ideas related to DSA, to improve my Dev skills ... I started with brainstorming a approximation algorithm to apply , because after searching and posting numerous blogs i eventually figured out that there is no other way to get the best answer other than to brute it exponentially. The algorithm i made is a mixture and modification of Floyd Warshal , Job Sequence Scheduling , travelling salesman and K-means Clustering. so first i implemented a console Version of this problem that included both Brute force (Exponential Brute) and the Clustering Approximation Algorithm ... with time comparison of both of them . After that I started working on a visual working simulator version which uses the same algorithm and here is the Final Working Product
•  » » » 7 weeks ago, # ^ |   0 Great work!