Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

So this may be a question that is born of my inability to properly express my intentions to Google.

In a fully connected non-directional graph such that any three points can be properly represented in a triangle in Euclidean geometry it would seem that a greedy first algorithm which chooses the shortest edge would find the shortest path from a starting point to visit all other points.

I can't find a condition under which this is false, but one of my neighbors (another programmer) insists that I am wrong, though still cannot come up with a condition where I am wrong.

Edit:

I am not sure this question is an instance of of the general TSP, which I know is NP hard, or if it is I thought that all of the constraints on the allowed graphs would have impacted the difficulty.

From wiki: TSP is the shortest possible route that visits each city exactly once and returns to the origin city. In this problem there is no requirement to return to the origin city. Further, we don't care about selecting the optimal origin city since the origin city is set in our specific example that we were discussing.

Additionally, the graph in this problem must conform to the constraints of euclidean distances in either 2 or 3 dimensions so a three node graph such as below (key is the node, val is the distances between other nodes) could not exist since the edge from A to B would make the edges from C to A and B infeasible.

A:{B:80, C:10}, B:{A:80, C:5}, C:{A:10, B:5}

Also by fully connected I meant all nodes have edges between them and every other node.

Sorry if the description came off as confusing, but I am wondering if given all these constraints, does it become solvable in a more simplistic manner.

share|improve this question
    
Its pretty unclear to me how your "greedy first" algorithm looks like. And does your graph have weighted edges? An example, maybe a picture would probably make your question clearer. –  Doc Brown Mar 23 at 8:30
    
Yes they are weighted edges, only positive weights. Edit: Also, it's a very dumb algo I am suggesting. Literally from a starting point pick the nearest point and go there, repeat. –  BSpiros Mar 23 at 8:36
    
This question is full of TSP and NP: sounds more like maths to me. –  david.pfx Mar 24 at 1:15

1 Answer 1

(Edit: Sorry, I missed that you wanted to visit all nodes in the graph, disregard my first answer, as I thought you wanted to find a path from point A to point B, rather than a path through every point.)

The name of the problem you're trying to solve is the Travelling Salesman Problem.

If you mean by "fully connected" a graph that is not disconnected, then it's the Euclidean plane version of the TSP, and it's NP-hard (although the algorithm you suggest is actually a pretty good heuristic).

If you take a graph that's a bunch of squares, like graph paper, picking the smallest edge would give lots of ties, and getting an optimal path by the algorithm you give would involve a whole lot of lucky guesses. This would be true even if you're talking about a complete graph (every node connected to every other node).

Edit: Since a fixed starting point was specified, I've got a counterexample. Take a triangle with nodes A, B, and C. Edge AC > edge BC > edge AB. Start at A, and we get AB, BC. Start at B and we get BA, AC. These are different paths with different lengths, so the algorithm given will not always give an optimal path.

The name for what you meant by "fully connected" is "complete". From wikipedia: "The requirement of returning to the starting city does not change the computational complexity of the problem, see Hamiltonian path problem."

share|improve this answer
    
Is this not a straight line? Edit: I really can't see how your answer works. Is there a 3 point graph where the shortest path to all three points from any specific point can be achieved by starting with the longest point? Specifically for a triangle the sum of any given two edges must be greater than the remaining edge, given this it would seem impossible that the shortest path could include the longest edge itself. –  BSpiros Mar 23 at 8:46
    
+1 for identifying the TSP from this very confusing problem description. I guess that's what the OP meant, but I am still not 100% sure. –  Doc Brown Mar 23 at 17:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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