Graphs

Project Euler 107: Determining the most efficient way to connect the network.

Project Euler 107: Determining the most efficient way to connect the network.

After the description of the disjoint set data structure (which I think you should read), it cannot come as a surprise what kind of solution we want to use for problem 107 of Project Euler. However, let as always start with the problem description:

The following undirected network consists of seven vertices and twelve edges with a total weight of 243.

The same network can be represented by the matrix below.

     A B C D E F G
A 16 12 21
B 16 17 20
C 12 28 31
D 21 17 28 18 19 23
E 20 18 11
F 31 19 27
G 23 11 27

However, it is possible to optimise the network by removing some edges and still ensure that all points on the network remain connected. The network which achieves the maximum saving is shown below. It has a weight of 93, representing a saving of 243 – 93 = 150 from the original network.

Using network.txt a text file containing a network with forty vertices, and given in matrix form, find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains connected.

Continue reading →

Posted by Kristian in Project Euler, 9 comments