CAT and MBA Entrance Preparation Module 3 – Data Interpretation and Logical Reasoning (DILR)
Routes, networks and flows
Find the shortest route in a small network by settling the nearest place first, count grid routes past a closed corner, and balance the flows at junctions.
What you will learn
- Find shortest and cheapest routes in a small network
- Count routes through a grid or a network with stated restrictions
- Balance the flows at junctions to fill a network's missing values
Before you start
What you’ll learn · Before you start
What you will learn
- Find shortest and cheapest routes in a small network
- Count routes through a grid or a network with stated restrictions
- Balance the flows at junctions to fill a network's missing values
Before you start
On this page
Six towns joined by nine roads hide a 14 km route from A to F that is hard to see by eye, a grid of streets 4 blocks by 3 holds 35 shortest walks, and three unknown flows at four junctions follow one from another.
Routes, networks and flows sets ask for exactly these: the shortest or cheapest route, the number of routes, and the missing flows. Each has a method that needs no guessing: settle the nearest place first, count routes by choosing when to turn, and balance every junction. A program checks every answer by trying every case.
The shortest route: settle the nearest town first
Six towns, A to F, are joined by nine roads, in kilometres: A–B 7, A–C 3, B–C 2, B–D 4, C–D 8, C–E 6, D–E 1, D–F 5 and E–F 7. What is the shortest route from A to F?
Small networks like this one already defeat the eye: the direct road A–B, 7 km, is longer than A–C–B, 5 km. Dijkstra's method: A way to find the shortest distances from one place: again and again, make final the unreached place with the smallest distance found so far and update its neighbours. It needs links of no negative length. gives A distance 0 and leaves every other town unreached. Then, again and again, it takes the unreached town with the smallest distance found so far, makes that distance final, and updates each neighbour whose distance the new town shortens. It needs roads of no negative length, and then no later route can beat a distance made final. Run on tolls instead of kilometres, the same steps find the cheapest route. Step through it, watching the table of distances:
- being compared or looked at
- being moved or written
- in its final place
- the key, pivot or target
- visited or ruled out
Pseudo-code
-
dist(start) ← 0; dist(v) ← ∞ for every other v; add start to the queue -
while the queue is not empty: -
u ← the queued node with the smallest dist; settle u -
for each edge u → v with weight w: -
if dist(u) + w < dist(v): dist(v) ← dist(u) + w; prev(v) ← u; queue v
| Node | dist | prev |
|---|---|---|
| A | 0 | — |
| B | ∞ | — |
| C | ∞ | — |
| D | ∞ | — |
| E | ∞ | — |
| F | ∞ | — |
Shortest distances from A. Every node starts at ∞ except A at 0. Each round settles the queued node with the smallest distance: with no negative weights, no later path can beat it.
When it finishes: A: 0, B: 5, C: 3, D: 9, E: 9, F: 14.
Try your own input
The towns become final in the order A 0, C 3, B 5, D 9, E 9 and F 14, so the shortest route is A–C–B–D–F, 14 km. The program checks it against every route that visits no town twice, and finds that with road B–D closed the best is A–C–E–D–F, 15 km:
"""Shortest routes, grid routes and flows, each checked two ways.
Part 1 runs Dijkstra's method on the lesson's six towns, settling the nearest
unsettled town each time, and checks the answer against every route that visits
no town twice. Part 2 counts the routes across a 4 by 3 grid that move only
right or up, by listing every move sequence and by adding counts point by point.
Part 3 fills the missing flows of the lesson's road network junction by junction.
"""
from itertools import permutations
from math import comb
ROADS = {("A", "B"): 7, ("A", "C"): 3, ("B", "C"): 2, ("B", "D"): 4, ("C", "D"): 8,
("C", "E"): 6, ("D", "E"): 1, ("D", "F"): 5, ("E", "F"): 7}
TOWNS = sorted({t for road in ROADS for t in road})
def length(a, b):
return ROADS.get((a, b)) or ROADS.get((b, a))
dist, came_from, settled = {t: None for t in TOWNS}, {}, []
dist["A"] = 0
while len(settled) < len(TOWNS):
town = min((t for t in TOWNS if t not in settled and dist[t] is not None), key=lambda t: (dist[t], t))
settled.append(town)
for other in TOWNS:
road = length(town, other)
if road and other not in settled and (dist[other] is None or dist[town] + road < dist[other]):
dist[other], came_from[other] = dist[town] + road, town
print("Settled in order:", ", ".join(f"{t} {dist[t]}" for t in settled))
route, t = ["F"], "F"
while t != "A":
t = came_from[t]
route.append(t)
print("Shortest A to F:", "-".join(reversed(route)), dist["F"], "km")
def every_route(closed=()):
"""Every route from A to F that visits no town twice, with its length."""
for k in range(0, 5):
for middle in permutations([t for t in TOWNS if t not in "AF"], k):
path = ("A", *middle, "F")
legs = list(zip(path, path[1:]))
if all(length(a, b) and {a, b} not in [set(r) for r in closed] for a, b in legs):
yield sum(length(a, b) for a, b in legs), path
km, path = min(every_route())
print("Every route checked: shortest", km, "km by", "-".join(path))
km, path = min(every_route(closed=[("B", "D")]))
print("With road B-D closed:", "-".join(path), km, "km")
print()
moves = {"".join(p) for p in permutations("RRRRUUU")}
print("Grid, 4 right and 3 up:", len(moves), "routes; C(7, 3) =", comb(7, 3))
def walk(seq):
x = y = 0
yield (x, y)
for m in seq:
x, y = (x + 1, y) if m == "R" else (x, y + 1)
yield (x, y)
through = sum((2, 1) in set(walk(m)) for m in moves)
print("Through the blocked point (2, 1):", through, "=", comb(3, 1), "x", comb(4, 2), "| avoiding it:", len(moves) - through)
count = {}
for y in range(4):
for x in range(5):
if (x, y) == (2, 1):
count[(x, y)] = 0
elif x == 0 and y == 0:
count[(x, y)] = 1
else:
count[(x, y)] = count.get((x - 1, y), 0) + count.get((x, y - 1), 0)
for y in range(3, -1, -1):
print(" " + " ".join(f"{count[(x, y)]:>3}" for x in range(5)))
print()
a = 500 - 200 # junction P: 500 in = a + 200 out
b = a + 150 - 100 # junction Q: a + 150 in = b + 100 out
c = 200 + 100 - 120 # junction R: 200 + 100 in = c + 120 out
print(f"Flows: a = {a}, b = {b}, c = {c}; junction S takes in {b + c} and sends out 530;"
f" the network takes in {500 + 150} and sends out {120 + 530}")Output
Settled in order: A 0, C 3, B 5, D 9, E 9, F 14
Shortest A to F: A-C-B-D-F 14 km
Every route checked: shortest 14 km by A-C-B-D-F
With road B-D closed: A-C-E-D-F 15 km
Grid, 4 right and 3 up: 35 routes; C(7, 3) = 35
Through the blocked point (2, 1): 18 = 3 x 6 | avoiding it: 17
1 4 7 11 17
1 3 3 4 6
1 2 0 1 2
1 1 1 1 1
Flows: a = 300, b = 350, c = 180; junction S takes in 530 and sends out 530; the network takes in 650 and sends out 650
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 routes.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Taking the shortest road out of each town
Always driving down the shortest road from where you are gives A–C–B–D–E–F: 3 + 2 + 4 + 1 + 7 = 17 km. The road D–E is short, but it leads away from F; only the distances from A tell which town to fix next.
Checkpoint
Check: Shortest routes, nearest town first
Grid routes: choose when to turn
A walker crosses a grid of streets 4 blocks east and 3 blocks north, always moving east or north. Every shortest walk has 7 moves, 4 east and 3 north, so a walk is fixed by choosing which 3 of the 7 moves go north: C(7, 3) = 35 routes.
If the corner 2 blocks east and 1 north is closed, subtract the walks through it: 3 ways to reach it, C(3, 1), times 6 ways to go on from it, C(4, 2), which is 18, so 17 walks avoid it. Adding gives the same: each corner’s count is the count of the corner to its west plus the corner to its south, with the closed corner set to 0. The program prints this table:
| Walks to each corner | 0 east | 1 east | 2 east | 3 east | 4 east |
|---|---|---|---|---|---|
| 3 north | 1 | 4 | 7 | 11 | 17 |
| 2 north | 1 | 3 | 3 | 4 | 6 |
| 1 north | 1 | 2 | closed | 1 | 2 |
| 0 north | 1 | 1 | 1 | 1 | 1 |
Checkpoint
Check: Grid routes by choosing when to turn
Flows: what enters a junction leaves it
Flows of traffic, water or money obey one rule at every junction: what comes in goes out, which the NIST dictionary calls flow conservation: The rule that at every junction of a network, apart from the points where flow enters or leaves it, what comes in equals what goes out, so each junction gives one equation.. So each junction gives one equation. On a network of one-way roads, 500 vehicles an hour enter at P and 150 at Q, while 120 leave at R and 530 at S. Roads run P to Q (a), P to R (200), Q to R (100), Q to S (b) and R to S (c), so three flows are missing. Start at a junction with only one unknown and work outwards:
The drawing shows the whole scene; its 5 steps are listed below.
Every step as text
- The network. Vehicles an hour on one-way roads. 500 enter at P and 150 at Q; 120 leave at R and 530 at S. The flows on P to Q, Q to S and R to S, called a, b and c, are missing.
- Junction P. Start where only one flow is missing. At P, 500 come in and a + 200 go out, so a = 300.
- Junction Q. Q now has one unknown. a + 150 = 450 come in, and b + 100 go out, so b = 350.
- Junction R. At R, 200 + 100 = 300 come in, and c + 120 go out, so c = 180.
- The check. S has nothing missing, so it checks the work. b + c = 350 + 180 = 530 come in and 530 leave. The whole network balances too, 650 in and 650 out.
P gives a = 300, then Q gives b = 350 and R gives c = 180. Junction S has nothing missing, so it checks the work: 530 in, 530 out, as the program’s last line shows.
Key idea
Balance one junction at a time, starting where only one flow is missing, and let a junction with nothing missing check the work.
Checkpoint
Check: Balancing flows at junctions
Practise: eleven questions on routes, walks and flows
Eleven untimed questions on the lesson’s network, grid and junctions and on new ones, weakest idea first; a question you miss comes back later.
Practice that adapts to you
Practise this lesson
11 questions about 5 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Five network and flow sets, fully worked Pro: opens with a Pro, Premium or Ultimate pass
Five sets that add tolls, one-way streets, a corner that must be passed, a road limit and a capacity to the three methods. A program tries every route, walk or flow of each set, so each answer can be checked.
In this part:
- Tolls: when the cheapest route is not the shortest, with worked numbers
- One-way streets: count by adding in order
- A grid with a corner to pass and one to avoid
- A loop of roads, and a range for one flow
- The most a network can carry
1 runnable example (Python) · about 5 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Restrictions that change the count: blocked points, one-way roads and must-pass places Pro: opens with a Pro, Premium or Ultimate pass
Four restrictions on the lesson’s grid and a count by turns, each worked by a rule and checked against all 35 walks, then the same idea for a shortest route that must pass a given town.
In this part:
- Five rules, each checked against every walk
- One-way streets in a grid, and turns
- A town the shortest route must pass
- Three slips that change the count
1 runnable example (Python) · about 4 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
Warm-up: how many routes cross a grid of m blocks east and n blocks north, moving only east or north?
C(m + n, n). Every such route has m + n moves, m of them east and n north, and it is fixed by choosing which n of the moves go north. A grid 4 blocks by 3 has C(7, 3) = 35 routes. A closed corner removes the routes through it, which are the routes to the corner times the routes from it to the end.
-
Fresher to mid
In a network of six towns, a candidate builds a route by always taking the shortest road out of the town they are in, and gets 17 km where the true shortest route is 14 km. Explain why the habit fails, and give a method that cannot fail on such a network.
-
Fresher to mid
A walker crosses a grid of streets 6 blocks east and 4 north, moving only east or north, and the corner 3 east and 2 north is closed. How many walks are possible? Show two ways to count, and say which you would trust in a test.
-
Fresher to mid
A network's junction equations leave one flow open. How do you answer "what is the largest flow road X can carry?" and "must road Y carry at least 40?", when no flow can be negative and each road carries at most 60?
Flashcards · 5 cards
Recall it, then check
Say the answer to yourself before you look: recalling it is what makes it stick.
-
How does Dijkstra's method find the shortest route?
Give the start 0, then keep making final the unreached place with the smallest distance found so far, updating its neighbours. With roads of no negative length, no later route can beat a final distance.
-
Why does taking the shortest road out of each town fail?
A short road can lead away from the goal: the greedy route through the six towns was 17 km, while settling the nearest town first gave A–C–B–D–F, 14 km.
-
How many shortest walks cross a grid of 4 blocks east and 3 north?
Every walk has 7 moves and is fixed by choosing which 3 go north: C(7, 3) = 35. In general C(m + n, n) for m blocks east and n north.
-
How do you count grid walks that avoid a closed corner?
Subtract the walks through it: ways to reach it times ways on from it. With the corner 2 east and 1 north closed, 3 × 6 = 18 pass through it, so 35 − 18 = 17 avoid it.
-
How do you find missing flows in a network?
What enters a junction leaves it, so each junction gives one equation. Start where only one flow is missing and work outwards; a junction with nothing missing checks the work.
Key takeaways
- Settle the nearest unreached town first: the six towns gave A–C–B–D–F, 14 km, and the shortest road out of each town gave 17.
- A grid walk is a choice of when to go north: C(7, 3) = 35 walks, 17 of them avoiding a closed corner.
- Every junction balances, so start where one flow is missing; a junction with nothing missing checks the work.
Terms in this lesson
- Dijkstra's method
- A way to find the shortest distances from one place: again and again, make final the unreached place with the smallest distance found so far and update its neighbours. It needs links of no negative length.
- flow conservation
- The rule that at every junction of a network, apart from the points where flow enters or leaves it, what comes in equals what goes out, so each junction gives one equation.
References
- A note on two problems in connexion with graphs (Numerische Mathematik 1, 1959) (Springer (E. W. Dijkstra))
- Dijkstra's algorithm (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology (NIST))
- flow conservation (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology (NIST))
- Mathematics, Class 11, Chapter 6: Permutations and Combinations (National Council of Educational Research and Training (NCERT))
- itertools: permutations and product (Python Software Foundation)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress