Graph models, BFS and weighted shortest paths

By UK A Level Computer Science · independent study · myAudience

Original textbook concept plate generated with OpenAI imagegen; labels and states checked against the lesson model. · Generated original teaching artwork; pending operator rights/provenance review before publication.

Graph models, BFS and weighted shortest paths

A graph consists of vertices and edges. Directed edges have an orientation; undirected edges connect in both directions. A weighted edge carries a value such as a nonnegative travel time. A path follows successive edges, and its weighted length is the sum of edge weights. The graph is an abstraction: in our fictional campus model, vertices are buildings and weights are walking minutes. A shortest path in that graph is only as meaningful as the selected times and accessibility assumptions. A mathematical minimum does not decide whether a route is safe or suitable for every person.

An adjacency list stores each vertex's outgoing neighbours and is efficient for sparse graphs. An adjacency matrix can test a particular edge in constant time but reserves Θ(V²) entries. In a directed graph, a→b does not imply b→a. Our implementations require every referenced neighbour to exist as a graph key. BFS additionally requires the starting key to exist. Invalid references should be rejected at a boundary in an application; the teaching functions state their accepted graph domain rather than pretending to validate every possible Python object. This implementation uses exact nonnegative integer weights, rejecting Boolean and floating-point weights. Floating-point additions can overflow even when individual edge weights are finite; silent infinity must not be interpreted as an unreachable vertex. A real measurement model needs an explicit numerical representation and overflow policy.

Breadth-first search uses a FIFO queue. It marks a vertex when first discovered, records its distance as its predecessor's distance plus one, and queues it once. The queue processes vertices in nondecreasing edge-count distance. If a shorter route to a newly discovered vertex existed, its predecessor would have been processed earlier, which contradicts first discovery through a longer layer. Thus BFS gives shortest path lengths in an unweighted graph. It does not minimise arbitrary total weights. Depth-first search instead follows a branch deeply, often using recursion or an explicit stack; it suits structural exploration but does not guarantee a shortest path on first discovery.

Dijkstra's algorithm maintains tentative distances and repeatedly processes a smallest outstanding distance. Relaxing u→v of weight w replaces d(v) if d(u)+w is smaller. Nonnegative weights ensure that an undiscovered continuation cannot return with a smaller distance than a settled minimum. A negative edge invalidates that reasoning. Our heap implementation keeps improved candidates and discards stale entries when their stored distance differs from the current best distance. This is a concrete representation choice; a hand-trace can use a simple table without reproducing heap internals.

With adjacency lists, BFS examines each reachable vertex and outgoing edge once, giving O(V+E) time and O(V) working storage. In the supplied lazy-heap Dijkstra implementation, there can be O(E) heap entries, yielding O((V+E) log(V+E)) time and O(V+E) working storage; on a simple graph this is commonly written O((V+E) log V). A dense table-based implementation has different costs. expects understanding and tracing of Dijkstra without recall of its complete steps. Writing and checking our original program deepens that foundation but does not turn implementation detail into an extra examination requirement.

Reading the diagram: Every arrow is directed and its adjacent integer is an edge weight: A→B=4, A→C=1, C→B=1, B→D=1, C→D=7. Teal marks the least-weight route A,C,B,D, whose sum is 3. The two tables answer different questions: weighted distances A 0,B 2,C 1,D 3 versus unweighted edge counts A 0,B 1,C 1,D 2. The direct-looking geometry is not an extra travel metric; only the declared edge weights count. Neither table proves the route is physically accessible or suitable.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
from collections import deque
import heapq

from collections import deque
import heapq

def bfs(graph, start):
"""Directed adjacency lists; all referenced vertices must be graph keys."""
distances = {start: 0}
queue = deque([start])
while queue:
vertex = queue.popleft()
for neighbour in graph[vertex]:
if neighbour not in distances:
distances[neighbour] = distances[vertex] + 1
queue.append(neighbour)
return distances

def dijkstra(graph, start):
"""Exact nonnegative integer weighted graph; keys and labels are strings."""
if start not in graph or any(v not in graph or type(w) is not int or w < 0
for edges in graph.values() for v, w in edges):
raise ValueError('invalid graph or nonnegative integer weight required')
distances = {start: 0}
heap = [(0, start)]
while heap:
distance, vertex = heapq.heappop(heap)
if distance != distances[vertex]:
continue
for neighbour, weight in graph[vertex]:
candidate = distance + weight
if candidate < distances.get(neighbour, float('inf')):
distances[neighbour] = candidate
heapq.heappush(heap, (candidate, neighbour))
return distances
```

Worked example: Use A→B=4, A→C=1, C→B=1, B→D=1, C→D=7. Find weighted distances from A, then compare BFS edge counts.

Start d(A)=0. Processing A gives d(B)=4 and d(C)=1.

Processing C next improves B to 2 and gives D=8. Processing B at distance 2 improves D to 3.

The later heap entries B=4 and D=8 are stale. The shortest A-to-D route is A,C,B,D with weight 3. BFS can reach D in two edges through B or C, ignoring weights.

Answer: Dijkstra gives A:0,C:1,B:2,D:3. BFS edge counts are A:0,B:1,C:1,D:2; these solve different objectives.

Check your understanding: 1. Why mark BFS vertices when enqueued? 2. What happens to disconnected vertices? 3. Add A→X=2, X→Y=−5 and A→Y=1 to a separate graph. Explain why settling Y at distance 1 is unsafe and what a correct specification must do.

Answer: 1. It prevents multiple predecessors from adding the same vertex repeatedly and preserves the first-discovery distance. 2. They remain absent from the returned reachable-distance map, not falsely assigned zero. 3. The later route A,X,Y has weight −3, so nonnegative-weight settling is unsound. Reject negative weights as this implementation does, or select an algorithm whose contract supports them and handle negative-cycle cases explicitly.

Why: A shortest path is defined by a metric; fewest edges and smallest weight differ. A directed edge has one direction. Disconnected does not mean zero distance. Nonnegative weights are a proof assumption, not an arbitrary cosmetic restriction.