Question

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 (i.e., edges).

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.

Answer 1

Consider stations as Vertex in graph and channels as edges. Assign 1 weight to all edges that are not compromised. Assign large weight like 10000 to all compromised channels. Apply single source shortest path algorithm to the graph (Dijkstra's algo below).

Algorithm->

->Create a set  that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
-> Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
->While set doesn’t include all vertices
…. Pick a vertex u which is not there in set and has minimum distance value.
…. Include u to set.
…. Relax all adjacent unvisited vertices. Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

Time complexity-> O(n*n) for adjacency matrix. Time complexity can be reduced to O(m + nLogn) using Fibonacci Heap implementation of dijkstra algorithm.