Saksham_Sahgal's blog

By Saksham_Sahgal, history, 10 days ago, In English

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)

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems like a pretty standard shortest path problem, where are you stuck at? what have you tried so far?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

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   Vote: I like it +12 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

        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 —

        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 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