d) Programming Assignment For the same network given in programming assignment 3
ID: 3843067 • Letter: D
Question
d) Programming Assignment For the same network given in programming assignment 3(c) the Sentinel Alarm Company wants to create a plan so that it can respond to emergency call from its customers in the shortest time. The locations and the travel time 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 routes and the travel time between the customers. Customers can be served from any one of these field stations. The company would like to create a plan that identifies which customer should be served from each of its field stations and the routes and distances that must be used by their service vehicles. Show how company can serve all its customers while minimizing the response time to its customers. Write a program to determine which customers must be served from each field stations. Show the minimum response times from the field stations to the customers. Print the list of routes (nodes) and the total travel time from the field stations to each of the customer location. 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
It is a simple graph question, we can store the data into a matrix with weight of the edges. This is a multiple source, single destination problem which can be achieved using Dijkstra's Algorithm or Bellman-Ford Algorithm, just make the source destination and destination source i.e. making the customer node as source and all the field stations as destination node, whatever destination nodes has least travelling time that can be choosen. You can find the implementation any where, here is the link:
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
For finding that one field station that minimizes the total cost of cable we can do a Floyd-Warshall algorithm. It will tell the minimum distance to all pairs and from that we can select the one node. Here is the algo:
final static int INF = 99999, V = 4;
void floydWarshall(int graph[][]) // it just takes the comple matrix
{
int dist[][] = new int[V][V];
int i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < V; k++)
{
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
If you are finding any difficulty in impleting do let me know !
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.