3 · The graph (without a library)

"Graph libraries are forbidden" sounds scary. In practice your graph is two dictionaries.

A map, drawn

This is maps/easy/02_simple_fork.txt: 4 drones, a junction that holds 2, then two paths to the goal.

start_hub: start 0 0
hub: junction 1 0 [max_drones=2]
hub: path_a 2 1
hub: path_b 2 -1
end_hub: goal 3 0
connection: start-junction [max_link_capacity=2]
connection: junction-path_a
connection: junction-path_b
connection: path_a-goal
connection: path_b-goal

Circles = zones (number inside = how many drones fit). Lines = connections (×n = how many drones may start crossing per turn). Nodes are placed at their x/y, but distance means nothing: every move costs 1 turn (2 into a restricted zone).

The same map, the way your code stores it

zones: name → Zone

{
  "start":    Zone(start, …),
  "junction": Zone(junction, …,
                   max_drones=2),
  "path_a":   Zone(path_a, …),
  "path_b":   Zone(path_b, …),
  "goal":     Zone(goal, …),
}

"Give me zone X" in one step.

neighbours: name → list of names

{
  "start":    ["junction"],
  "junction": ["start", "path_a",
               "path_b"],
  "path_a":   ["junction", "goal"],
  "path_b":   ["junction", "goal"],
  "goal":     ["path_a", "path_b"],
}

"Where can I go from X?" in one step. This is the adjacency list.

That's the whole "graph" BFS, Dijkstra and every other pathfinding algorithm only ever ask one question: "where can I go from here?". neighbours[here] answers it. You already did this in A-Maze-ing, where the neighbours were the open walls of a cell.

One connection, two entries

A connection goes both ways, so add_connection writes it into both zones' lists:

Forget one direction and drones can travel a connection only one way. That's a classic bug.

Finding a connection again: the frozenset key

When a drone moves from path_a to junction, you need that connection's capacity. But the file wrote it as junction-path_a. The order must not matter:

Key type	`a-b`	`b-a`	Same key?
`tuple`	`("junction", "path_a")`	`("path_a", "junction")`	✗ different
`frozenset`	`{"junction", "path_a"}`	`{"path_a", "junction"}`	✓ equal

So connections is a dict keyed by frozenset({a, b}), and link(u, v) looks up frozenset({u, v}). The same key also makes the parser's duplicate check trivial: "is this key already in the dict?"

Your first algorithm on it: BFS

Before anything with capacity or time, write plain BFS on neighbours. It gives you two things you need anyway:

Is the goal reachable at all?

Skip blocked zones. If BFS never reaches the end, the map is unsolvable. The subject says to report that clearly, not as a parse error and not by looping forever.

How far is each zone?

For the fork: start 0, junction 1, path_a/path_b 2, goal 3. So a single drone needs 3 turns, and that's a lower bound for the whole map.

Check yourself

What is neighbours["junction"] for the fork map?
Why must add_connection append to two lists?
What does link("goal", "path_b") look up, exactly?
Where do blocked zones get skipped: in the Network or in BFS?