Connecting a Set of Vertices into an optimally weighted graph

Question

This is essentially the problem of connecting n destinations with the minimal amount of road possible.

The input is a set of vertices (a,b, ... , n)

The weight of an edge between two vertices is easily calculated (example the cartesian distance between the two vertices)

I would like an algorithm that given a set of vertices in euclidian space, returns a set of edges that would constitute a connected graph and whose total weight of edges is as small as it could be.

In graph language, this is the Minimum Spanning Tree of a Connected Graph.

With brute force I would have:

1. Define all possible edges between all vertices - say you have n vertices, then you have n(n-1)/2 edges in the complete graph
2. A possible edge can be on or off (2 states)
3. Go through all possible edge on/off combinations: 2^(n(n-1)/2)!
4. Ignore all those that would not connect the graph
5. From the remaining combinations, find the one whose sum of edge weights is the smallest of all

I understand this is an NP-Hard problem. However, realistically for my application, I will have a maximum of 11 vertices. I would like to be able to solve this on a typical modern smart phone, or at the very least on a small server size.

As a second variation, I would like to obtain the same goal, with the restriction that each vertex is connected to a maximum of one other vertex. Essentially obtaining a single trace, starting from any point, and finishing at any other point, as long as the graph is connected. There is no need to go back to where you started. In graph language, this is the Open Euclidian Traveling Salesman Problem.

Some pseudocode algorithms would be much helpful.

Answer 1

Ok for the first problem you have to build a Minimum Spanning Tree. There are several algorithms to do so, Prim and Kruskal. But take a look also in the first link to the treatment for complete graphs that it is your case.

For the second problem, it becomes a little more complicated. The problem becomes an Open Traveling Salesman Problem (oTSP). Reading the previous link maybe focused on Euclidean and Asymmetric.

Regards

Answer 2

Maybee you could try a greedy algorithm:

1. Create a list sortedList that stores each pair of nodes i and j and is sorted by the 
   weight w(i,j).
2. Create a HashSet connectedNodes that is empty at the beginning
3. while (connectedNodes.size() < n)
     element := first element of sortedList
     if (connectedNodes.isEmpty())
       connectedNodes.put(element.nodeI);
       connectedNodes.put(element.nodeJ);
       delete element from sortedList
     else 
       for(element in sortedList) //start again with the first
         if(connectedNodes.get(element.nodeI) || connectedNodes.get(element.nodeJ))
           if(!(connectedNodes.get(element.nodeI) && connectedNodes.get(element.nodeJ)))
              //so it does not include already both nodes
              connectedNodes.put(element.nodeI);
              connectedNodes.put(element.nodeJ);
              delete element from sortedList
              break;
           else 
              continue;

So I explain step 3 a little bit:

You add as long nodes till all nodes are connected to one other. It is sure that the graph is connected, because you just add a node, if he has a connection to an other one already in the connectedNodes list.

So this algorithm is greedy what means, it does not make sure, that the solution is optimal. But it is a quite good approximation, because it always takes the shortest edge (because sortedList is sorted by the weight of the edge).

Yo don't get duplicates in connectedNodes, because it is a HashSet, which also make the runtime faster.

All in all the runtime should be O(n^2) for the sorting at the beginning and below its around O(n^3), because in worst case you run in every step through the whole list that has size of n^2 and you do it n times, because you add one element in each step.

But more likely is, that you find an element much faster than O(n^2), i think in most cases it is O(n).

Answer 3

You can solve the travelsalesman problem and the hamilton path problem with the optimap tsp solver fron gebweb or a linear program solver. But the first question seems to ask for a minimum spanning tree maybe the question tag is wrong?

Answer 4

For the first problem, there is an O(n^2 * 2^n) time algorithm. Basically, you can use dynamic programming to reduce the search space. Let's say the set of all vertices is V, so the state space consists of all subsets of V, and the objective function f(S) is the minimum sum of weights of the edges connecting vertices in S. For each state S, you may enumerate over all edges (u, v) where u is in S and v is in V - S, and update f(S + {v}). After checking all possible states, the optimal answer is then f(V).

Below is the sample code to illustrate the idea, but it is implemented in a backward approach.

const int n = 11;
int weight[n][n];
int f[1 << n];
for (int state = 0; state < (1 << n); ++state)
{
    int res = INF;
    for (int i = 0; i < n; ++i)
    {
        if ((state & (1 << i)) == 0) continue;
        for (int j = 0; j < n; ++j)
        {
            if (j == i || (state & (1 << j)) == 0) continue;
            if (res > f[state - (1 << j)] + weight[i][j])
            {
                res = f[state - (1 << j)] + weight[i][j];
            }
        }
    }
    f[state] = res;
}
printf("%d\n", f[(1 << n) - 1]);

For the second problem, sorry I don't quite understand it. Maybe you should provide some examples?