Skip to content

Problem 107: Determining the most efficient way to connect a network

September 26, 2010

The 107th Euler Problem aims to calculate the most efficient way to connect a given network. This is definitely a problem that can be solved using graphs, i.e. it’s a typical minimum spanning tree (MST) problem (Prim’s algorithm).

Please note that the code below is just a snapshot of the original code. If one wants to check the entire code, please go to my github repository.

I started by creating a class to represent the graph. My representation uses an adjacency matrix, however for space-saving purpose I could have used adjacency lists instead.

public class Graph {

	public int nvertices;
	public int[][] edges;

        ...

Then I created a Prim’s class which has a method to calculate the minimum spanning tree of a given graph. The method, named prim, is explained below together with the class:

public class Prim {

  public Graph g;
  public int start;

  private final int MAXINT = Integer.MAX_VALUE;
  private int[] distance;
  private int[] parent;

As one can see, there are a number of global variables: the graph, the starting node, the maximum integer value (explained below) and two arrays – one containing the distances and another containing the parents. These are very important variables for the prim’s method below:

public int prim() {
  //Variables for loops and saving information
  int i, v, weight, dist;
  //Total amount saved by creating a MST
  int save = 0;
  //Number of vertices
  int nVertices = this.g.getNvertices();
  //Current elements in the final tree
  boolean[] intree = new boolean[nVertices];

  //Initialization of the arrays
  for (i=0; i < nVertices; i++) {
    intree[i] = false;
    this.distance[i] = this.MAXINT;
    this.parent[i] = -1;
  }

These first lines initialize the helper variables and the arrays which will hold the information regarding the MST. Furthermore, the following code is the responsible for creating the MST and calculate the total saved:

  //Starting point
  this.distance[this.start] = 0;
  v = this.start;

  //Loop through the vertices
  while(intree[v] == false) {
    intree[v] = true;

    // Search all adjacent nodes and update distances
    for(int j=0; j<nVertices; j++) {
      weight = this.g.edges[v][j];
      if (weight != 0) {
	if((this.distance[j] > weight) &&
	   intree[j] == false) {
	  if (this.distance[j] != this.MAXINT)
	    save += this.distance[j];
	  this.distance[j] = weight;
	  this.parent[j] = v;
	}
	else if (intree[j] == false)
	       save += weight;
      }
    }

    //Find out next vertice to explore
    v = 0;
    dist = this.MAXINT;
    for(i=0; i< nVertices; i++) {
	if ((intree[i] == false) &&
	    (dist > this.distance[i])) {
	  dist = this.distance[i];
	  v = i;
	}
    }
  }

  //Return the total saved
  return save;

For the scope of this problem, the save variable is important since it is accumulating the total savings during the process of building the MST. Then it was a matter of parsing the input file into a matrix and pass it on to the Prim’s class in order to perform the calculations. The Main class is also available in my github repository.

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: