PyQdeck LogoPyQdeckSubjectsSyllabusBlog
Back to the 2024 paper

Module 3: Graph and Tree Algorithms

20242m

Which algorithm is typically used in maximum flow problems?
(i) Kruskal's Algorithm
(ii) Floyd-Warshall
(iii) Ford-Fulkerson
(iv) Prim's Algorithm

Search GoogleAsk AI
Worked SolutionAI Assisted

Answer: (iii) Ford-Fulkerson

Explanation:

  • Maximum Flow problem: given network with capacities c(u,v)c(u,v), find flow ff maximizing value from ss to tt respecting capacity and conservation.
  • Ford-Fulkerson method (and Edmonds-Karp O(VE2)O(VE^2) implementation, Dinic, Push-relabel) repeatedly finds augmenting paths in residual graph and augments until none remain; correctness via max-flow min-cut theorem.
  • Kruskal/Prim = MST, Floyd-Warshall = APSP, not flow.

Correct choice: (iii) Ford-Fulkerson (also Edmonds-Karp, Dinic are refinements).

Similar questions

Design and Analysis of Algorithms Which of the following algorithms is commonly used to find the Minimum Spanning Tree of a graph? (i) Dijkstra's Algorithm (ii) Kruskal's Algorithm (iii) Bellman-Ford Algorithm (iv) Floyd-Warshall Algorithm20252mDesign and Analysis of Algorithms Which of the following algorithm solves the All Pair Shortest Path problem (i) Dijkstra's (ii) Floyd's Warshall's (iii) Prim's (iv) Kruskal's20222mDesign and Analysis of Algorithms Which algorithm is used to find a Minimum Spanning Tree? (i) Dijkstra's algorithm (ii) Prim's algorithm (iii) Bellman-Ford algorithm (iv) Floyd-Warshall algorithm20242mDesign and Analysis of Algorithms Which of the following algorithms is used to find the minimum spanning tree in a weighted undirected graph? (i) Dijkstra's algorithm (ii) Kruskal's algorithm (iii) Bellman-Ford algorithm (iv) Floyd-Warshall algorithm20232m
PreviousTopological sorting is only possible in: (i) Undirected Graphs (ii) Trees (iii) Directed Acyclic Graphs (iv) Weighted GraphsNextWhat is the primary technique used to prove that a problem is NP-complete? (i) Divide and conquer (ii) Dynamic programming (iii) Polynomial-time reduction from a known NP-complete problem (iv) Space complexity calculation
Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

Install Pocketly