For the following 2 questions you can use any of the algorithms studied in class
ID: 3575668 • Letter: F
Question
For the following 2 questions you can use any of the algorithms studied in class. You do not have to write full descriptions of the algorithms. Just indicate which algorithm you would use, and which changes you need to make to the algorithm to answer each question. Indicate also how to pre-process the input for the algorithm. For example, if the question is: given a road map with distances between cities, find a shortest way of driving from city A to city B; your answer might be: build a graph in which every node is a city and an edge represents a road. The length of an edge Ls the length of the corresponding road. Use Dijkstra's algorithm to find a shortest path from A to B. This is a shortest route to drive from A to B. Let G = (V, E) be a graph representing a communication network in which the edges are labelled either slow or fast. Describe an algorithm for finding a path from vertex s to vertex t with the smallest number of slow edges (it does not matter how many fast edges there are in the path as long as the number of slow edges is as small as possible).Explanation / Answer
First assign to each slow edge of G a length of n.
And to every fast edge a length of 1.
Then use Dijkstra’s algorithm to find out a shortest path between s to t. As we know that, slow edges have cost more than any simple path formed by the fast edges, this shortest path will then minimize the number of slow edges.