Ford Fulkerson Algorithm: Irrational Capacities. The Ford-Fulkerson algorithm ma

Question

Ford Fulkerson Algorithm: Irrational Capacities. The Ford-Fulkerson algorithm may not terminate when arc capacities are allowed to be irrational. To see this consider the above maximum flow problem. Assume that all the arc capacities are infinite, except for the two bold arcs shown with capacities gamma and gamma^2. Here we set gamma = 5 - 1/2 to be the golden ratio.^1 Show that there is an infinite sequence of augmenting paths P_1, P_2, P_3,... such that the Ford-Fulkerson will never terminate if it augments along these paths in each iteration.

Explanation / Answer

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class FordFulkerson { private int[] parent; private Queue queue; private int numberOfVertices; private boolean[] visited; public FordFulkerson(int numberOfVertices) { this.numberOfVertices = numberOfVertices; this.queue = new LinkedList(); parent = new int[numberOfVertices + 1]; visited = new boolean[numberOfVertices + 1]; } public boolean bfs(int source, int goal, int graph[][]) { boolean pathFound = false; int destination, element; for(int vertex = 1; vertex

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.