A map becomes useful when it can answer a route question
A student at the Main Gate wants to reach the Innovation Lab. Several walkways are available, and the route with the fewest edges may not have the least distance. Construction can also close a road temporarily, so the best route must be calculated from the current network rather than stored permanently.
The program models locations as vertices and bidirectional walkways as weighted edges. The edge weight is distance in metres. Given a starting location and destination, it must compute the minimum total distance and print every location on that path.
Network
Seven named campus locations connected by roads.
Cost
Each open road has a positive distance.
Change
Closing a road removes both directions immediately.
Define observable behaviour before coding
| Operation | Precondition | Postcondition |
|---|---|---|
| Find route | Two valid locations | Print shortest path and total metres, or report unreachable |
| Close road | An open direct edge exists | Both matrix directions become INF |
| Open/update road | Different vertices; positive distance | Both matrix directions store the new weight |
| Display network | None | Print each undirected road exactly once |
Design assumptions
- All walkways are bidirectional, so the matrix is symmetric.
- Every valid edge weight is positive; zero appears only on the diagonal.
- The graph is small enough for an adjacency matrix and O(V²) Dijkstra.
- A closed or absent edge uses
INF, not weight zero. - Location names are stable and their indices are the program’s vertex identifiers.
Represent the campus as a weighted undirected graph
Vertex: campus location Edge: direct open walkway Weight: walking distance in metres distance[u][v] = distance[v][u]
An adjacency matrix gives constant-time edge lookup and makes road updates direct. It stores V² entries even when only a few roads exist. This is acceptable for seven locations and keeps the algorithm visible to learners.
| Representation | Edge lookup | Neighbour scan | Best fit |
|---|---|---|---|
| Adjacency matrix | O(1) | O(V) | Small or dense graphs; chosen here |
| Adjacency list | O(degree) typical | O(degree) | Large sparse graphs |
| Edge list | O(E) | O(E) | Algorithms that process all edges, such as Kruskal |
Three arrays used by Dijkstra
best[v]: smallest known distance from source to v.visited[v]: whether v’s minimum distance has been finalised.previous[v]: predecessor that produced the current best distance; used to reconstruct the path.
Conditions that must remain true
- The diagonal remains zero: travelling from a vertex to itself has no cost.
- For this undirected graph,
distance[u][v] == distance[v][u]. - An unavailable edge is represented by INF in both directions.
- Every finite non-diagonal edge weight is strictly positive.
- When a vertex becomes visited, its
bestvalue is final under Dijkstra’s non-negative-weight assumption. - If
previous[v] = u, then u was on the best known route used to update v. - A destination is unreachable exactly when its final best value remains INF.
Relaxation improves routes one edge at a time
Initialise every best distance to INF, except the source which is zero. Repeatedly select the unvisited vertex with the smallest best value. For each neighbour, evaluate a route that first reaches the current vertex and then crosses the edge.
candidate = best[current] + weight(current, neighbour)
if candidate < best[neighbour]:
best[neighbour] = candidate
previous[neighbour] = currentThe comparison is called relaxation. It does not immediately prove the neighbour is final; it records a better known route. Finalisation happens when that neighbour later becomes the minimum unvisited vertex.
Path reconstruction
Starting from the destination, follow previous until -1. This produces the path backwards, so store vertices in a temporary array and print them in reverse order. Distance alone cannot reconstruct the route; the predecessor relationship is essential.
Compiler-ready C11 program
Loading source…Implementation reading order
Graph state
Read initialization, connect and sample-road loading.
Shortest path
Trace nearestUnvisited, relaxation and printPath.
Live updates
Verify road closure and reopening update both directions.
INF is defined below INT_MAX so adding a practical edge to a finite route does not overflow. The relaxation expression is reached only when the current vertex has a finite best distance.
Trace Main Gate to Innovation Lab
- Initialise source at Main Gate.
- Finalise Main Gate.
- Finalise Admin Block.
- Finalise Library.
- Finalise CSE Block.
- Finalise Innovation Lab.
- Reconstruct path.
- Display result.
Press Next to begin.
Test cost, connectivity and updates
Test 1 — Known shortest path
Test 2 — Source equals destination
Test 3 — Road closure changes result
Test 4 — Unreachable destination
Test 5 — Symmetric update
Test 6 — Invalid input
Complexity depends on representation
| Operation | Current implementation | Alternative | Reason |
|---|---|---|---|
| Dijkstra | O(V²) | O((V+E) log V) | Linear minimum selection vs binary heap with adjacency list |
| Road lookup/update | O(1) | O(degree) list scan | Direct matrix indexing |
| Display roads | O(V²) | O(V+E) | Scan upper triangle vs list entries |
| Path reconstruction | O(V) | O(V) | A simple path contains at most V vertices |
| Graph storage | O(V²) | O(V+E) | Full matrix vs sparse adjacency list |
For a small campus, clarity and constant-time updates make the matrix reasonable. For a national road network, an adjacency list plus priority queue is far more appropriate.
Check the route-planning logic
Which array is required to print the route, not just its distance?
Which algorithm should replace Dijkstra if negative edge weights are allowed?
Extension challenges
- Replace the matrix with adjacency lists and use a binary min-heap.
- Support directed one-way walkways and identify which invariants change.
- Offer “shortest distance” and “least walking time” as different cost modes.
- Compute alternative routes that do not share the same critical edge.
- Add A* search with coordinates and an admissible straight-line heuristic.
Defend the algorithm and its limits
Why does Dijkstra require non-negative weights?
It permanently finalises the smallest unvisited distance. A later negative edge could create a cheaper path to an already finalised vertex, invalidating that greedy decision.
Why not use breadth-first search?
BFS minimises the number of edges only when edges are unweighted or have equal cost. Campus roads have different distances, so fewer roads does not necessarily mean fewer metres.
When is Floyd–Warshall preferable?
When routes between many or all pairs are repeatedly required and O(V³) preprocessing plus O(V²) storage is acceptable. Dynamic closures would require recomputation or more advanced handling.
How does a priority queue improve Dijkstra?
It retrieves the smallest tentative distance in logarithmic time instead of scanning all vertices. With adjacency lists this yields O((V+E) log V) for a binary heap.
What changes for a directed graph?
Opening u→v no longer implies v→u. The symmetry invariant is removed, updates touch one direction unless explicitly requested, and reachability can differ by travel direction.
The shortest path is a claim supported by maintained state
The graph represents what movement is currently possible; Dijkstra maintains the best known costs; the predecessor array explains how the answer was obtained. Correct routing requires all three, along with an explicit non-negative-weight assumption.