hw

CS5200 Homework – 4 (Deadline: 11-30-2023 11:59pm) Instructor: Huiyuan Yang Question 1 Verify that f 0 is a flow. Let b be augmentation amount. Capacity constraint: If ( u; v ) 2 P is a forward edge then f 0 ( e ) = f ( e ) + b and b ≤ c ( e ) - f ( e ). If ( u; v ) 2 P is a backward edge, then letting e = ( v; u ), f 0 ( e ) = f ( e ) - b and b ≤ f ( e ). Both cases 0 ≤ f 0 ( e ) ≤ c ( e ). Conservation constraint: Let v be an internal node. Let e 1 ; e 2 be edges of P incident to v . Four cases based on whether e 1 ; e 2 are forward or backward edges. 1

2

for k in range(nV): for i in range(nV): for j in range(nV): distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]) print_solution(distance) # Printing the solution def print_solution(distance): for i in range(nV): for j in range(nV): if(distance[i][j] == INF): print("INF", end=" ") else: print(distance[i][j], end=" ") print(" ") G = [[0, 3, INF, 5], [2, 0, INF, 4], [INF, 1, 0, INF], [INF, INF, 2, 0]] floyd_warshall(G) Explanation: 1. Initialization:  nV : Number of vertices in the graph (4 in this case).  INF : A constant representing infinity, used to initialize distances. 2. Algorithm Implementation:  The function floyd_warshall takes an adjacency matrix G as input.  It initializes a distance matrix to store the shortest distances between all pairs of vertices. The initial values are set to the values in the input matrix G . 4

 The algorithm iterates over all vertices ( k ) and updates the distance matrix based on the shortest paths. 3. Printing the Solution:  The function print_solution prints the resulting distance matrix.  If the distance between vertices i and j is infinity ( INF ), it prints "INF". Otherwise, it prints the actual distance. 4. Given Graph (G):  The provided graph is represented as an adjacency matrix, where G[i][j] represents the weight of the edge from vertex i to vertex j . 5. Function Call:  The Floyd-Warshall function is called with the provided graph G . The result is printed, showing the shortest distances between all pairs of vertices. 5

7

kij dij (k-1) dik(k-1) dkj(k-1) dij(k) nij(k) 111 0 0 0 0 Nil 112 1 1 2 5 0 113 0 0 0 8 8 114 9 0 9 9 1 121 8 - - - Nil 122 0 - - - Nil 123 7 8 8 0 8 124 0 0 9 0 Nil 131 3 3 0 3 3 132 8 3 5 8 1 133 0 3 0 Nil 1 134 3 9 12 1 1 141 0 0 - Nil Nil 142 4 5 4 4 1 143 8 8 4 1 1 144 0 9 0 Nil Nil An st -cut (cut) is a partition ( A , B ) of the nodes with s ∈ A and t ∈ B . Def. Its capacity is the sum of the capacities of the edges from A to B . 8