Algorithm Homework Pseudo code please Jen has been getting d

Algorithm Homework: (Pseudo code please!)

Jen has been getting desperate lately because of the network: Portions of it can become disconnected, or “blankety-blank close to being disconnected,” as she so colorfully puts it. She wonders how few edges would have to fail so that there would be no paths at all between her node and her friend Ali’s. We could call this fewest number of edges the Jen-Ali connectivity of the network Figure out how Jen can determine the Jen-Ali connectivity of the network, given a description of the network. (Does this have anything to do with a minimum cut?) Then design a fast algorithm to compute this special connectivity, and analyze the time for your algorithm. And hurry, because Jen’s future happiness may hang in the balance!

Solution

This is exactly the minimum cut i.e. we need to find minimum number of edges that make the graph disconnected. By the mention of minimum cut in the question itself, I assume that you are familiar with it.

1. Create residual graph as equal to the original graph of network.

2. Run Ford-Fulkerson algorithm for maximum flow, and get the final residual graph when algorithm terminates.

3. Mark all vertices as either reachable/non-reachable from source ( Jen ) in the residual graph

4. The required edges are the ones, which are from reachable vertices to non-reachable vertices.