Euclidean Space Fully Connected Nondirectional Graph: Shortest Path to all nodes

Question

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.

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

Answer 2

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.