Answer of assignment 5 r 3 Minimum cut: Vs={s, V1}, Vt = {v2, v3, v4, v5, t} r 7
Download 155.28 Kb.
|
1 2
- Navigate this page:
- C - 8.3 Employ and modify the Dijkstra algorithm. Algorithm
- Return
Step5: length=4 
C-8.3 Employ and modify the Dijkstra algorithm. Algorithm ModifiedDijkstra_largest_augment_residual_capacity (G, s, t) Input: A flow net work G, source s and sink t. Output: The augment path with the largest residual capacity for all u Î G.vertices() if u s D[u] ¥; else D[u] 0; P[u] = null; Let Q be a priority queue that contains all the vertex of G using D labels as keys. while ØQ.isEmpty() u ¬ Q.removeMax() for each vertex z such that there is an edged between u and z and z is in Q if D[z] min(D[u],  ) then // where is the residual capacity on the edge from u to z
D[z] ß min(D[u], )
P[z] = “u”; Change to D[z] the key of z in Q If (D[t] = =0) output=“There is no augmenting path” Else
c=”t”; // where t is the sink While(c!=null) output=c+output; c=P[c];
Return Output The time complex the same as that of Dijstra’s algorithm, which is O((n+m)logn). C-8.9 This problem can be translated to a minimum-cost maximum flow problem: Let X be a set of nodes with each representing a taxi, Y be a set of nodes with each representing a location. Put a directed edge between each pair of {taxi, location} such that the direction is from taxi to location and the cost of the edge is the distance between them. Add a source node s and a sink node t. For each taxi, add a directed edge from s to it. For each location, add a directed edge from it to t. Each edge is given a capacity of 1. Find a minimum-cost maximum flow on this network. In the resulting flow, if the edge between taxi xi and location yj has a flow value of 1, then send xi to yj. Download 155.28 Kb. Share with your friends:
|
1 2