0
$\begingroup$

I have got a problem with an excercise about graphs:

Your friend has been hired by a brewery to work out the most efficient delivery route for the beer-delivery truck drivers. A typical delivery has about 50 stops and the company wants to save money by driving the shortest possible distance. Your friend ignores your advice and decides on an algorithm, as follows:

  • Start at the depot,
  • Go to the nearest location that has not yet been delivered to:
    • Deliver
    • Repeat until you have delivered all the beer
  • Return to depot

And the quesiton is: What is the Big-O complexity of this approach? Why?

I do not think this way of solving problem is any algorithm like Prim's algorithm, and I have no clue what can be a complexity. Could anyone explain me?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ It depends on how you implement it. The description is too abstract to figure that out. Actually, given that there are "about 50 stops" the complexity is $O(1)$, but I doubt that's the answer you're looking for... $\endgroup$ – Tom van der Zanden Apr 28 '16 at 12:50
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael♦ Apr 28 '16 at 13:30
  • 1
    $\begingroup$ Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael♦ Apr 28 '16 at 13:31
  • $\begingroup$ Hint: depending on how the input is given, linear running time is possible. How? $\endgroup$ – Raphael♦ Apr 28 '16 at 13:32
2
$\begingroup$

This problem looks variant of TSP problem(more precisely metric TSP). As you want to traverse all node with the minimum distance.

TSP is one of the classical NP-Hard problem.

What your friend did is a Greedy approach making minimum Spanning tree Which is 2-Approx(metric-TSP) of the minimum distance.

This greedy approach generally works in E log V time but does not have guarantee for exact solution.

By using graph structure we can implement in linear time also.

|cite|improve this answer
$\endgroup$
-2
$\begingroup$

E(logV) where E is the number of edges in the graph and V is the number of nodes i.e. here number of stops=50 So, E log50 will be the time complexity

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.