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.


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.

  • 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 '14 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 '14 at 8:36
  • This question is full of TSP and NP: sounds more like maths to me. – david.pfx Mar 24 '14 at 1:15

(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."

  • 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 '14 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 '14 at 17:11
  • If by "pretty good" you mean "in the same order as optimal", then greedy is not a good heuristic for euclidean TSP; you'd use one of the simple constant-factor approximations, for example building an MST and using a DFS walk on that gives you a 2-approximation in loglinear time. – G. Bach Apr 11 '16 at 12:53

Simple counter example. Let's place all points on the X-axis. The points are at -1, 0.1, 1, and 2. The shortest link in this graph is from 0.1 to 1. The greedy algorithm takes this path, then greedily continues to 1, then 2, then it is forced to take the longest possible link to reach -1. The total length is 4.9.

The shortest route is either to start at one of the ends (length 3), or if we still start at 0.1 then we should go to -1 first, then 1 then 2, for a length of 4.1.

If you want any three points to form proper triangles, you can give each point a random Y value in the ballpark of 1/1000th. That will not meaningfully change the lengths or the route.

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.