Reference no: EM133210511

Question 1) Suppose that CONTROL, a secret U.S. government counterintelligence agency based in Washington, D.C., has build a communication network that links n stations spread across the world using m communication channels between pairs of stations. Suppose further that the evil spy agency, KAOS, is able to eavesdrop on some number, k, of these channels and that CONTROL knows the k channels that have been compromised. Now, CONTROL has a message, M, that it wants to send from its headquarters station, s, to one of its field stations, t. The problem is that the message is super secret and should traverse a path that minimizes the number of compromised edges that occur along this path. Explain how to model this problem as a shortest-path problem, and describe and analyze an efficient algorithm to solve it.

Question 2) Draw a simple, connected, weighted, undirected graph with 8 vertices and 16 edges, and with distinct edge weights. Identify one vertex as a "start" vertex and illustrate a running of Dijkstra's algorithm on this graph.

Question 3) Show how to modify Dijkstra's algorithm to not only output the distance from v to each vertex in G, but also to output a tree Trooted at v, such that the path in T from v to a vertex u is actually a shortest path in G from v to u.

Question 4) Suppose you are given a connected weighted undirected graph, G, with n vertices and m edges, such that the weight of each edge in G is an integer in the interval 1,c, for a fixed constant c>0. Show how to solve the single-source shortest-paths problem, for any given vertex v, in G, in time O(n+m).

Hint: Think about how to exploit the fact that the distance from v to any other vertex in G can be at most O(cn)=O(n).