Suppose that CONTROL a secret US government counterintellige

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.

Solution

We can use a graph to model the source(headquarters station) s and the destination(field station) t. There are other nodes in this graph, which are the rest of the field stations. The shortest path problem is where we take the graph, and minimize the cost of traversing between the source and destination. Here, we need to minimize number of compromised edges in the path.

1. Take a cost vector, and for each vertex, compute the cost to reach it. Set Res={} has the vertices for the result.

2. cost(s)=0 and cost of the rest of the edges is set to infinity.

3. Initialize a array, Q where Q has all the verices of graph G.

4. In a loop, take the minimum (min) in Q.

5. For each node adjacent to minimum node min, if C(min) + W_s,min < c(min), then c(min) is changed to c(s) + W_s,min .

6. Go to step 4.

7. Result is the path from S to T. Where, we keep a track of all the edges used in getting up to a particular T.

Performance Analysis:

The runtime complexity of this algorithm in O(n^2) . G has n vertices and m edges. Step 4 occurs at most of n times.Finding the minimum has an upperbound of n^2. Hence the complexity becomes, O(n^2).