ENCN205 — Lab 4: Network Routing

Duration: 2–3 hours · Format: Python (Jupyter notebook) · Prerequisites: Labs 1–3 · Assessment: sign-off quiz on LEARN

1Learning Objectives

Explain how a road network is represented as a graph of nodes, edges and weights
Build a graph (a Python dictionary) from a GeoDataFrame of road segments
Implement Dijkstra's shortest-path algorithm from pseudocode and test it
Snap real-world locations to the nearest network node and route between them
Compare the shortest (distance) and fastest (time) routes
Model a disruption — bridge closures — and quantify the detour it causes
Compute and map a travel-time service area (isochrone)

2Engineering Scenario

You work for the emergency management team at Christchurch City Council. On 22 February 2011 several bridges over the Avon River / Ōtākaro in the eastern suburbs were damaged and closed, cutting the usual routes between New Brighton and the central city. You will build a routing tool — the engine behind every navigation app — on the real Christchurch road network (about 970 km of road from OpenStreetMap), then use it to measure how much the closures lengthened the trip from the eastern suburbs to Christchurch Hospital.

Start as usual: conda activate encn205, then jupyter lab, then open Lab4_NetworkRouting.ipynb and run the cells in order with Shift + Enter. The data file data/christchurch_roads.gpkg must sit in a data folder next to the notebook.

3Step-by-Step Instructions

Section 1: Setup and Loading the Road Network

Load the four layers of christchurch_roads.gpkg (edges, nodes, places, rivers) and plot an overview map showing the network, the rivers and every bridge that spans a river.

Section 2: From Roads to a Graph

Learn the graph vocabulary — nodes, edges, weights — and build an adjacency dictionary graph[u][v] = weight from the edges layer. Your turn: build a second graph weighted by travel time and compare it with the distance-weighted one.

Section 3: Dijkstra's Algorithm

Read the pseudocode, follow the hand-worked trace on a six-node toy network, then write the algorithm yourself by filling in the selection and relaxation steps. A test cell checks your function against the worked example — do not move on until it passes.

Section 4: Routing on the Real Network

Snap places to their nearest node, then route New Brighton Pier to Christchurch Hospital on the time graph and on the distance graph. Compare the two routes and read the street list. Your turn: repeat for Sumner Beach and quantify the minutes lost on the shortest-distance route.

Section 5: Interactive Map

Draw both routes on a zoomable web map with .explore(), reprojecting to WGS84 first.

Section 6: Disruption — The 2011 Bridge Closures

List the road bridges over the Avon, close Pages Road and reroute. Your turn: close the six eastern bridges at once, reroute New Brighton Police Station to the hospital, report the extra minutes and map the detour. Then rank the bridges by the delay each one causes on its own.

Section 7: Service Area

Run Dijkstra without a target to get the drive time from the hospital to every intersection, and map it as an isochrone. A second map shows the extra minutes caused by the closures.

Section 8: Summary and Reflection

Review the key ideas, then answer the reflection questions — they are good preparation for the sign-off quiz and the exam.

4Assessment: Lab Sign-Off

This lab is not complete until you have submitted your sign-off to LEARN.

Step 1 — Self-check

Before you start the quiz, make sure you can do each of these:

Built distance- and time-weighted graphs from the edges layer
Implemented dijkstra() and passed the toy-network tests
Routed between two real places and explained why the fastest and shortest routes differ
Modelled the 2011 bridge closures and reported the extra travel time
Interpreted the service-area (isochrone) map

Step 2 — Take the sign-off quiz

Download Lab4_SignOff.html from LEARN and open it in your web browser.
Enter your full name and University ID, then answer the 10 questions. Keep the notebook open — several questions ask about numbers you computed.
You need 8 out of 10 to pass. You can retake it as often as you like — each attempt draws a new set of questions, and every answer comes with an explanation.
When you pass, click Download Sign-Off PNG. This saves a file called ENCN205_Lab4_<yourID>.png.

Step 3 — Submit

Upload ENCN205_Lab4_<yourID>.png to the Lab 4 Sign-Off submission on LEARN.

The PNG records your name, ID, score, and a timestamp inside the QR code. It's your proof of completion — show it to your tutor if they ask.

Tips and Troubleshooting

Symptom	Fix
The toy-network `assert` fails	Add `print(current, distance)` inside the loop and compare each pass with the hand-worked table. Most errors are in the relaxation test: it must be `new_distance < distance[neighbour]`.
`KeyError` when routing on the real network	You are mixing graphs: a node removed by a closure is not in that graph. Route with the graph you built from the same edges.
`reconstruct_path` returns an empty list	The target was never reached — check that you passed the right graph and that the source and target are node ids (integers), not place names.
A route takes many seconds	Normal for a full service-area run (about a second). If a single route is slow, make sure your loop `break`s when `current == target`.
Interactive map shows nothing or is untrusted	Re-run the cell; convert to WGS84 with `.to_crs(epsg=4326)` before `.explore()`. Offline, the tiles will not load but the routes still draw.
Snapped node is far from the place	Expected for a few hundred metres — places sit beside roads, not on intersections. Use `nodes.distance(point).idxmin()` exactly as in Section 4.