Reference no: EM132382440

Question

Your good friend, Johnny, who also lives in Manchester, is turning 18 in a few months. To celebrate the occassion you would like to give Johnny a birthday card that has been signed by all of his friends.

The only problem is Johnny is incredibly well travelled, and has friends all through the country and the world. Figure out the best way to get the card to all of these friends before Johnny's birthday, you have turned to graph theory. Every city and town in which a friend of Johnny lives has been allocated a number between 1 and the number of friends (minus one), and Manchester has been allocated the number 0. You have recorded postage times between locations as edge weights.

You have found that all pairs of locations are such that the postage time from A to B is the same as the postage time from B to A, so your graph is undirected. You have also found that there is a postage connection between every pair of locations, so your graph is connected and complete. You have implemented this graph as an adjacency matrix, where each cell represents the weight of an edge.

All postage times are given in integers, representing how many days the card would take to travel between the two locations. (I.e. an edge weight of 2 between A and B means it would take two days to get the card between location A and location B.)

Part A)

Create function post_time(graph, path) that returns how long it will take Johnny's card to travel the given path using divide and conquer

Input: a nested list graph that represents a graph as an adjacency matrix, that models the postage routes and times between Johnny's friends; and a

List of integers path that represents a proposed path in the graph. You may assume the given path exists in the graph.

Output: an integer that is the number of days it would take Johnny's card to travel the given path.

Examples

postage1 = [ [0,1,1,3,2], [1,0,4,5,1], [1,4,0,1,3], [3,5,1,0,1], [2,1,3,1,0] ]

postage2 = [ [0,2,2,1,2], [2,0,1,1,2], [2,1,0,1,4], [1,1,1,0,1], [2,2,4,1,0] ]

a) Calling post_time(postage1, [0,1,4,3,2,0]) returns 5.

b) Calling post_time(postage1, [0,3,1,2,3]) returns 13.

Part B)

Create function post route(graph) that uses a greedy approach to ?nd a fast (but not necessarily the fastest) route by which to send the card.

The metric for the greedy approach is: send the card to the location that takes the shortest time to get to that the card has not yet been visited; or, if all locations

have been visited, send the card back to Manchester. If there are multiple locations to chose from, all with the same distance, choose the location that has been allocated the smaller number.

Input: a nested list graph that represents a graph as an adjacency matrix, that models the postage routes and times between Johnny's friends.

Output: a list of integers, where each integer is a location, ordered such that visiting each location in the order given creates a cycle that begins and ends in Manchester. The only number that can appear twice is 0.

Examples

a) Calling post route(postage1) returns [0,1,4,3,2,0].

b) Calling post route(postage2) returns [0,3,1,2,4,0].