The ABC Utility Company wants to lay cable lines from its field stations to its

Question

The ABC Utility Company wants to lay cable lines from its field stations to its customers. The locations and the distances between adjacent customers and the field stations are shown in the figure below. The field stations are located at nodes 7, 14, 25, 28, and 40. Remaining nodes show the locations of its customers. The edges show the possible cable routes and the distance between the customers. Customers can be served from any one of these switching stations. Show how company can serve all its customers while minimizing the total cable used. You do not need exclusive cables from field stations to its customers. The cable lines can be extended from customer to another, but all customers must be served from one of its field stations. Write a program to determine the edges along which the cables must be laid. Show the final layout of the cables lines. You can draw final cable layout plan by hand. What is the total length of the cable used? If you could build only one field station that minimizes the total cost of the cable used, which node(s) would you choose for your field station?

Explanation / Answer

The figure showing the distances between adjacent customers and field stations is not given.

Please do not forget to rate the answer.

From the question, it is clear that we need to find the minimum path from stations to each of the customers.

Since the figure is not given in the question, I have assumed the below diagram

           2 3
(0)--(1)--(2)
| / |
6| 8/  |7
| / |
(3)-------(4)
      
Numbers within () is the vertex.
Numbers without () is the distance value.

That is number on the edges will represent the distance from one vertex to another.
For example, to reach from node/vertex 0 to node 1, the distance is 2. From node 1 to node 4, it is 5 etc.

For this graph, if we write a matrix it is as below,
                               {0, 2, 0, 6, 0},
                                   {2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},

Similar to the above matrix, from the figure (in the problem), a matrix can be constructed.
With the help of below code, the minimum distance in the given matrix sufficient to make
the graph connected will be obtained.
This information could be used to lay out the cable lines.

CODE:

// Below code uses the Prim's Algorithm to find the Minimum Spanning Tree (MST)

import java.util.*;
import java.lang.*;
import java.io.*;

class MST
{
   // Number of vertices in the graph harcoded.
   private static final int V=5;

   // Function to find the vertex with minimum key
   // value, from the set of vertices not yet included in MST
   int minimumKey(int key[], Boolean inputMatrix[])
   {
       int min = Integer.MAX_VALUE, minIndex=-1;

       for (int v = 0; v < V; v++)
           if (inputMatrix[v] == false && key[v] < min)
           {
               min = key[v];
               minIndex = v;
           }

       return minIndex;
   }

  
   // Find MST using Prim's Algorithm.
   void primMST(int graph[][])
   {
       // Key values used to pick minimum weight edge in cut
       int key[] = new int [V];

       // Array to store constructed MST
       int parent[] = new int[V];
      
       // To represent set of vertices not yet included in MST
       Boolean mstMatrix[] = new Boolean[V];

       // Initialize all keys to large value.
       for (int i = 0; i < V; i++)
       {
           key[i] = Integer.MAX_VALUE;
           mstMatrix[i] = false;
       }

       // Always include first 1st vertex in MST.
       // Here we take vertex 0 as first vertex.
       key[0] = 0;     
       parent[0] = -1;

       // MST will have V count of vertices
       for (int count = 0; count < V-1; count++)
       {
           // Pick the minimum key vertex from the set of vertices not yet included in MST
           int u = minimumKey(key, mstMatrix);

           // Add the picked vertex to the MST Set
           mstMatrix[u] = true;

           // Update key value and parent index of the adjacent
           // vertices of the picked vertex for the set of vertices not yet included in MST
           for (int v = 0; v < V; v++)

               if (graph[u][v]!=0 && mstMatrix[v] == false &&
                   graph[u][v] < key[v])
               {
                   parent[v] = u;
                   key[v] = graph[u][v];
               }
       }

       // print the constructed MST
       printMST(parent, V, graph);
   }

   // To print the MST
   void printMST(int parent[], int n, int graph[][])
   {
       System.out.println("Sufficient Edge Weight to keep graph connected are: ");
       for (int i = 1; i < V; i++)
           System.out.println(parent[i]+" - "+ i+" "+
                           graph[i][parent[i]]);
   }

   public static void main (String[] args)
   {
       MST t = new MST();
       // Matrix corresponds to the example shown earlier
       int graph[][] = new int[][] {{0, 2, 0, 6, 0},
                                   {2, 0, 3, 8, 5},
                                   {0, 3, 0, 0, 7},
                                   {6, 8, 0, 0, 9},
                                   {0, 5, 7, 9, 0},
                               };

       t.primMST(graph);
   }
}

OUTPUT:
Sufficient Edge Weight to keep graph connected are:
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5

This says vertex 0 to vertex 1 the best route has distance 2 and so on.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.