Search code examples
algorithmcomplexity-theorygraph-algorithmminimum-spanning-treetraveling-salesman

Connecting a Set of Vertices into an optimally weighted graph

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.

Solution

  • 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