Specify most efficient roads connecting Seattle, San Francisco, Los Angeles, New York, and Miami (see details)

Question

I've been puzzled by the idea of building efficient roads based on the following criteria:
1) Minimize total length of roads built (each mile costs 1 point)
2) Minimize distance required to travel between any two cities specified (each mile costs one point, with total distance score = sum of roads required to travel between all distinct pairs of cities)

Notes:
Ignore existing roads in this problem. You are building roads from scratch.

Ignore topography. You can build roads anywhere.

Roads do not need to connect two cities directly... you can have "ghost nodes" between cities that roads connect through, if that makes your system more efficient.

Where would you put the roads to minimize total points? What technique did you use to determine your solution?

No, I'm not in college taking a final exam. I'm just personally curious about this problem.

Answer 1

I would think Steiner Trees might be useful in this situation (link 1).

Using an applet I found on the web (link 2) for heuristically solving Steiner Trees, I estimated the positions of Seattle, San Francisco, Los Angeles, New York and Miami. It connected these nodes as follows.
1) Los Angeles and San Francisco got connected at a node just east of San Francisco.
2) This new node connected to Seattle through a node in eastern Oregon.
3) Miami and New York got connected to a node around West Virginia.
4) The node in Oregon and the node in West Virginia got connected across the country.

I overlaid this on the original map of the US and it looks like the attached picture:

http://img176.imageshack.us/img176/6573/steinermap5nodeshs9.jpg

Now this isn't very exact because we are using flat coordinates on a plane and these cities are really on the surface of a sphere, but you get the idea.

Contrary to the other answer, there is much more to it than just finding a single node in the middle and connecting everything to it.

Have fun playing with the applet. I must have spent a good 45 minutes just picking points and watching it connect them with lines.

Answer 2

put all these five on the corners of a pentagon and join all of them to a point equidistant from all and build roads to this point.
Now whereever you want to go, first go to this point and then to your destination.