Study guide

15.11 Network Flow Models: Shortest Route, Maximal Flow & Spanning Tree

Coal India Management Trainee CIL MT

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: CIL MT Exam Overview & Coal Sector Landscape

1.1 CIL MT Exam Pattern, Marking Scheme & Strategy 1.2 Coal India Limited: Corporate Structure, Maharatna Status & Subsidiaries 1.3 Indian Coal Mining Sector, Energy Mix & Environmental Regulations

2 Chapter 2: Paper-I General Awareness, Polity & Current Affairs

2.1 Indian Constitution, Governance & Statutory Bodies 2.2 Indian Economy, Union Budget & Economic Planning 2.3 Indian Geography, Mineral Belts & Environmental Ecology 2.4 Modern Indian History, Freedom Struggle & Cultural Heritage 2.5 General Science: Physics, Chemistry & Biology Fundamentals 2.6 Inventions, Discoveries & Scientific-Technological Development 2.7 Uses of Internet, Computer Awareness & Digital Governance 2.8 National & International Organisations 2.9 Awards, Honours & Sports 2.10 Books & Authors, Important Monuments & Places of India 2.11 Ports, Power Plants & Infrastructure of India 2.12 Climate Change, SDGs, National Parks & Wildlife Sanctuaries 2.13 Flagship Government Programmes & Current Affairs Method 2.14 World Physical, Social & Economic Geography

3 Chapter 3: Paper-I Reasoning & Logical Ability

3.1 Series Completion, Coding-Decoding & Semantic Analogies 3.2 Syllogisms, Logical Deduction & Venn Diagrams 3.3 Seating Arrangements, Linear/Circular Alignments & Puzzles 3.4 Direction Sense, Blood Relations & Order/Ranking 3.5 Alphabetical & Alphanumeric Series 3.6 Statement & Conclusions, Statement & Arguments 3.7 Clocks & Calendars 3.8 Cubes, Dice & Figure Counting 3.9 Mirror Images, Water Images, Embedded Figures & Non-Verbal Series 3.10 Decision Making & Data Analysis in Reasoning

4 Chapter 4: Paper-I Numerical Ability & Quantitative Aptitude

4.1 Arithmetic Foundations: Percentages, Profit & Loss, Ratio & Proportion 4.2 Averages, Simple/Compound Interest, Alligations & Mixtures 4.3 Time & Work, Pipes & Cisterns, Time, Speed & Distance 4.4 Algebra, Mensuration, Geometry & Data Interpretation (DI) 4.5 Number System, LCM, HCF & Decimal Fractions 4.6 Surds, Indices & Simplification 4.7 Problems on Ages 4.8 Boats & Streams and Problems on Trains 4.9 Permutations & Combinations 4.10 Probability for Quantitative Aptitude

5 Chapter 5: Paper-I General English & Verbal Ability

5.1 English Grammar, Error Spotting & Sentence Correction 5.2 Vocabulary Building: Synonyms, Antonyms, Idioms & Phrases 5.3 Reading Comprehension, Cloze Tests & Para Jumbles 5.4 Fill in the Blanks, Cloze Passages & Sentence Completion 5.5 Jumbled Sentences & Sentence Improvement

6 Chapter 6: Paper-II Engineering Mathematics

6.1 Matrix Algebra, Rank & Systems of Linear Equations 6.2 Eigenvalues, Eigenvectors & the Cayley-Hamilton Theorem 6.3 Limits, Continuity, Differentiability & Mean Value Theorems 6.4 Maxima-Minima, Indeterminate Forms & Taylor Series 6.5 Definite, Improper, Double & Triple Integrals 6.6 Partial Derivatives, Total Derivative & Multivariable Optimisation 6.7 First-Order Differential Equations: Linear & Non-Linear 6.8 Higher-Order Linear Differential Equations & Engineering Applications 6.9 Laplace Transforms & Transfer-Function Methods 6.10 Probability, Conditional Probability & Bayes' Theorem 6.11 Random Variables, Distributions & Descriptive Statistics 6.12 Numerical Methods: Root Finding, Integration & ODE Solvers

7 Chapter 7: Paper-II Engineering Mechanics & Statics-Dynamics

7.1 Force Systems, Coplanar Equilibrium & Lami's Theorem 7.2 Plane Trusses, Friction Mechanics & Screws/Wedges 7.3 Centroids, Center of Gravity & Moment of Inertia 7.4 Kinematics, Kinetics of Particles & Rigid Body Dynamics 7.5 Virtual Work & Lagrange's Equation 7.6 Rolling Friction, Belt-Pulley Drives, Brakes, Clutches & Vehicle Dynamics

8 Chapter 8: Paper-II Mechanics of Materials & Structural Integrity

8.1 Simple Stresses, Strains, Elastic Moduli & Thermal Stresses 8.2 Principal Stresses, Strain Energy & Mohr's Circle 8.3 Shear Force & Bending Moment Diagrams, Beam Bending & Shear Stresses 8.4 Torsion of Circular Shafts, Springs & Column Buckling 8.5 Thin Cylinders, Spheres & Thick-Walled Pressure Vessels 8.6 Deflection of Beams: Double Integration, Macaulay & Moment-Area 8.7 Shear Centre & Unsymmetrical Bending 8.8 Strain Gauges, Rosettes & Experimental Stress Analysis 8.9 Mechanical Testing: Universal Testing Machine, Hardness & Impact

9 Chapter 9: Paper-II Theory of Machines & Mechanical Vibrations

9.1 Simple Mechanisms, Kinematic Inversions & Velocity/Acceleration Diagrams 9.2 Cams & Followers, Toothed Gearing & Epicyclic Gear Trains 9.3 Flywheels, Centrifugal/Inertia Governors & Rotor Balancing 9.4 Free, Damped & Forced Single-Degree-of-Freedom Vibrations 9.5 Gyroscopic Couple & Gyroscopic Effects

10 Chapter 10: Paper-II Machine Design & Failure Theories

10.1 Static Failure Theories & Variable/Fatigue Loading 10.2 Design of Threaded Fasteners, Welded & Riveted Joints 10.3 Design of Shafts, Keys, Couplings & Rolling/Sliding Bearings 10.4 Design of Spur, Helical, Bevel & Worm Gears 10.5 Design of Helical, Leaf & Torsion Springs 10.6 Design of Brakes & Clutches: Energy, Lining Pressure & Heat

11 Chapter 11: Paper-II Fluid Mechanics & Hydraulic Machinery

11.1 Fluid Properties, Hydrostatic Forces & Buoyancy 11.2 Fluid Kinematics, Continuity & Bernoulli's Equation 11.3 Viscous Flow in Pipes, Boundary Layer & Minor Losses 11.4 Hydraulic Turbines, Centrifugal & Reciprocating Pumps 11.5 Dimensional Analysis, Similitude & Model Testing 11.6 Control-Volume Analysis: Continuity, Momentum & Energy

12 Chapter 12: Paper-II Thermodynamics, Thermal Cycles & Turbomachinery

12.1 Fundamental Concepts, First & Second Laws of Thermodynamics 12.2 Entropy, Availability, Exergy & Properties of Pure Substances 12.3 Air-Standard Gas Power Cycles: Otto, Diesel, Dual & Brayton 12.4 Vapour Power Cycles: Ideal, Reheat & Regenerative Rankine Cycles 12.5 Thermodynamic Relations: Maxwell, Clausius-Clapeyron & Joule-Thomson 12.6 Behaviour of Ideal & Real Gases and Equations of State 12.7 Air & Gas Compressors: Reciprocating, Rotary & Multi-Stage 12.8 Steam & Gas Turbines: Impulse, Reaction & Velocity Diagrams

13 Chapter 13: Paper-II Heat Transfer, Refrigeration & Air Conditioning

13.1 Steady & Unsteady Conduction, Extended Surfaces (Fins) 13.2 Forced/Natural Convection, Radiation & Heat Exchanger LMTD/NTU 13.3 Vapour Compression & Vapour Absorption Refrigeration Systems 13.4 Psychrometric Properties, Processes & Air Conditioning Systems 13.5 Gas Refrigeration, Heat Pump Cycles & Cryogenics

14 Chapter 14: Paper-II Materials Science, Metallurgy & Manufacturing Technology

14.1 Crystal Structures, Phase Diagrams & Iron-Iron Carbide Equilibrium 14.2 Heat Treatment Processes & Engineering Alloy Steels 14.3 Casting Processes, Metal Forming & Welding Metallurgy 14.4 Metal Cutting Mechanics, Tool Life & Machine Tools 14.5 Plastic Deformation, Yield Criteria & Load Estimation in Bulk Forming 14.6 Sheet Metal Forming: Shearing, Bending & Deep Drawing 14.7 Powder Metallurgy 14.8 Brazing, Soldering & Adhesive Bonding 14.9 Non-Traditional Machining: EDM, ECM, USM, AJM, LBM & EBM 14.10 Abrasive Machining, Grinding & Superfinishing 14.11 Principles of Work Holding, Jigs & Fixtures 14.12 Economics of Machining & Tool Life Optimisation

15 Chapter 15: Paper-II Metrology, Quality Control & Industrial Engineering / OR

15.1 Limits, Fits, Tolerances, Gauges & Surface Metrology 15.2 Production Planning, Forecasting & Inventory Control Models 15.3 Operations Research: Linear Programming & Transportation/Assignment 15.4 Project Management: CPM, PERT, Network Analysis & Crashing 15.5 Comparators & Interferometry 15.6 Coordinate Measuring Machines & Machine Tool Alignment Testing 15.7 Computer Integrated Manufacturing: CAD/CAM & Integration Tools 15.8 NC/CNC Machines & CNC Part Programming 15.9 Material Requirements Planning, Scheduling & Sequencing 15.10 Queuing Theory & Simple Queuing Models 15.11 Network Flow Models: Shortest Route, Maximal Flow & Spanning Tree

15.11 Network Flow Models: Shortest Route, Maximal Flow & Spanning Tree

Key Takeaways Explain This Topic AI

Network flow models are named explicitly in the Operations Research bullet of the CIL Mechanical Paper-II syllabus, separately from PERT and CPM.

The shortest route problem finds the minimum-cost path between two nodes and is solved systematically by Dijkstra's labelling algorithm.

The maximal flow through a network equals the capacity of the minimum cut, which is the max-flow min-cut theorem.

A minimum spanning tree connects all n nodes using exactly n minus 1 arcs at least total cost, and is found greedily by Kruskal's or Prim's algorithm.

Last updated: August 2026

Network Terminology

A network is a set of nodes connected by arcs . Each arc may carry a length, a cost, a time or a capacity depending on the problem.

  • Term Meaning
  • Node (vertex) A junction, location or state
  • Arc (edge, branch) A connection between two nodes
  • Directed arc Flow permitted in one direction only
  • Undirected arc Flow permitted in either direction
  • Path A sequence of arcs connecting two nodes
  • Cycle (loop) A path that returns to its starting node
  • Tree A connected network containing no cycles
  • Spanning tree A tree containing all nodes of the network
  • Connected network Every node reachable from every other

A key structural fact used repeatedly: a spanning tree of an n n n -node network contains exactly n − 1 n-1 n − 1 arcs . Fewer leaves it disconnected; more creates a cycle.

The Operations Research bullet of the syllabus lists network flow models separately from PERT and CPM. Project networks are treated in the project-management section; this section covers the three classical flow problems.

The Shortest Route Problem

Find the minimum-total-length path from a source node to a destination. The arc values may be distance, time or cost.

Dijkstra's labelling algorithm

Label the source node permanently with 0.

From the most recently permanently labelled node, give each directly connected unlabelled node a temporary label equal to the permanent label plus the connecting arc length. If it already has a temporary label, keep the smaller of the two.

Among all temporary labels, make the smallest permanent .

Repeat from step 2 until the destination is permanently labelled.

Backtrack from the destination to recover the route.

The algorithm requires non-negative arc lengths, which is always satisfied by physical distances, times and costs.

Worked example

A network of haul roads connects the pit (node 1) to the washery (node 6):

  • Arc Length (km)
  • 1-2 4
  • 1-3 2
  • 2-4 5
  • 3-2 1
  • 3-5 8
  • 2-5 10
  • 4-6 6
  • 5-6 3

Step by step:

Node 1 permanent at 0 .

Temporary: node 2 gets 4, node 3 gets 2. Smallest is node 3, so node 3 permanent at 2 .

From node 3: node 2 gets 2 + 1 = 3 2 + 1 = 3 2 + 1 = 3 , which beats its existing 4, so update to 3. Node 5 gets 2 + 8 = 10 2 + 8 = 10 2 + 8 = 10 . Smallest temporary is node 2 at 3, so node 2 permanent at 3 .

From node 2: node 4 gets 3 + 5 = 8 3 + 5 = 8 3 + 5 = 8 ; node 5 gets 3 + 10 = 13 3 + 10 = 13 3 + 10 = 13 , worse than 10, so keep 10. Smallest is node 4 at 8, so node 4 permanent at 8 .

From node 4: node 6 gets 8 + 6 = 14 8 + 6 = 14 8 + 6 = 14 . Smallest temporary is node 5 at 10, so node 5 permanent at 10 .

From node 5: node 6 gets 10 + 3 = 13 10 + 3 = 13 10 + 3 = 13 , which beats 14, so update. Node 6 permanent at 13 .

The shortest route is 1 - 3 - 5 - 6 with total length 13 km . Note that the direct-looking route through node 2 and node 4 is longer at 14 km, and that node 2's label was improved from 4 to 3 during the process — the step candidates most often skip.

The Maximal Flow Problem

Find the greatest flow that can be pushed from a source to a sink when each arc has a limited capacity . Applications include water and slurry pipelines, conveyor networks, ventilation circuits and traffic on haul roads.

The max-flow min-cut theorem

A cut is a set of arcs whose removal disconnects the source from the sink. The capacity of a cut is the sum of the capacities of its forward arcs.

The maximum flow from source to sink equals the capacity of the minimum cut.

This is one of the most elegant results in operations research and it has an immediate practical reading: the bottleneck is a set of arcs, not a single arc. Increasing the capacity of any arc not in the minimum cut achieves nothing at all.

The augmenting path algorithm

Find any path from source to sink with spare capacity on every arc.

Determine the bottleneck , the smallest remaining capacity along that path.

Push that amount of flow along the path, reducing the forward capacity of each arc by it and increasing the reverse capacity by the same amount.

Repeat until no augmenting path remains.

The total pushed is the maximum flow; verify against the minimum cut.

The reverse-capacity step in stage 3 is essential rather than cosmetic. It permits later iterations to cancel an earlier flow assignment that turns out to be suboptimal, and without it the algorithm can terminate short of the true maximum.

Worked example: maximal flow

A slurry network runs from source S to sink T:

  • Arc Capacity
  • S-A 10
  • S-B 8
  • A-C 6
  • A-B 4
  • B-C 5
  • B-D 7
  • C-T 9
  • D-T 6

Augmenting paths:

S-A-C-T : bottleneck is min ⁡ ( 10 , 6 , 9 ) = 6 \min(10, 6, 9) = 6 min ( 10 , 6 , 9 ) = 6 . Push 6. Remaining: S-A 4, A-C 0, C-T 3.

S-B-D-T : bottleneck is min ⁡ ( 8 , 7 , 6 ) = 6 \min(8, 7, 6) = 6 min ( 8 , 7 , 6 ) = 6 . Push 6. Remaining: S-B 2, B-D 1, D-T 0.

S-B-C-T : bottleneck is min ⁡ ( 2 , 5 , 3 ) = 2 \min(2, 5, 3) = 2 min ( 2 , 5 , 3 ) = 2 . Push 2. Remaining: S-B 0, B-C 3, C-T 1.

S-A-B-C-T : bottleneck is min ⁡ ( 4 , 4 , 3 , 1 ) = 1 \min(4, 4, 3, 1) = 1 min ( 4 , 4 , 3 , 1 ) = 1 . Push 1. Remaining: C-T 0.

No further path exists, since both C-T and D-T are saturated. Maximum flow = 6 + 6 + 2 + 1 = 15.

Check against the minimum cut: the cut { C - T , D - T } \{C\text{-}T,\; D\text{-}T\} { C - T , D - T } has capacity 9 + 6 = 15 9 + 6 = 15 9 + 6 = 15 . The cut { S - A , S - B } \{S\text{-}A,\; S\text{-}B\} { S - A , S - B } has capacity 10 + 8 = 18 10 + 8 = 18 10 + 8 = 18 . The minimum is 15, matching the flow. Confirmed.

The engineering conclusion is that upgrading the S-A pipeline would achieve nothing; only enlarging C-T or D-T raises throughput.

The Minimum Spanning Tree Problem

Connect all nodes at least total cost, with no requirement that any particular pair be connected directly. Applications include laying power cables to a group of mine substations, routing a compressed-air ring main, and planning a communication network.

The distinction from the shortest route problem is worth stating explicitly: shortest route connects two specified nodes by the cheapest path; minimum spanning tree connects all nodes at least total cost. They generally give different answers.

Kruskal's algorithm (arc-based)

Sort all arcs in ascending order of cost.

Add arcs one at a time in that order, skipping any arc that would form a cycle .

Stop when n − 1 n - 1 n − 1 arcs have been added.

Prim's algorithm (node-based)

Start from any node.

Repeatedly add the cheapest arc connecting a node already in the tree to one not yet in it.

Stop when all n n n nodes are included.

Both are greedy algorithms and both are guaranteed to reach a true optimum for this problem — which is unusual, since greedy methods generally do not. Prim's is easier to apply by hand because it never requires an explicit cycle check.

Worked example

Six substations are to be connected by cable:

  • Arc Cost Arc Cost
  • 1-2 5 3-4 4
  • 1-3 3 3-5 8
  • 2-3 6 4-5 2
  • 2-4 7 4-6 9
  • 5-6 6

Applying Kruskal, arcs in ascending order: 4-5 (2), 1-3 (3), 3-4 (4), 1-2 (5), 5-6 (6), 2-3 (6), 2-4 (7), 3-5 (8), 4-6 (9).

Add 4-5 (2). Tree has 1 arc.

Add 1-3 (3). 2 arcs.

Add 3-4 (4). 3 arcs. This links the two fragments.

Add 1-2 (5). 4 arcs.

Next is 5-6 (6). Add it. 5 arcs.

With n = 6 n = 6 n = 6 nodes we need n − 1 = 5 n - 1 = 5 n − 1 = 5 arcs, and we have them. The arcs 2-3, 2-4, 3-5 and 4-6 are all rejected, either because five arcs suffice or because they would close a cycle.

Minimum spanning tree cost = 2 + 3 + 4 + 5 + 6 = 20 = 2 + 3 + 4 + 5 + 6 = \textbf{20} = 2 + 3 + 4 + 5 + 6 = 20 .

Summary of the Three Problems

  • Problem Objective Method Arc attribute
  • Shortest route Cheapest path between two nodes Dijkstra labelling Length, time or cost
  • Maximal flow Greatest throughput source to sink Augmenting paths; verify by min cut Capacity
  • Minimum spanning tree Connect all nodes at least cost Kruskal or Prim Cost

A common examination trap is to present a minimum spanning tree problem in language that sounds like a shortest route problem, or the reverse. The test is simple: if the requirement is to link every location, it is a spanning tree; if it is to travel from one specified place to another , it is a shortest route.