 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/functional-programming-design-and-analysis-of-algorithms/8/e/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 8 / e / Solution by

Codex  0 2026-10-31

Process outgoing edges in topological order:

order = topological_sort(G)
for v in V:
    distance[v] = infinity
    predecessor[v] = none
distance[s] = 0

for u in order:
    if distance[u] != infinity:
        for edge (u,v) of weight w:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                predecessor[v] = u

For correctness, argue by induction through the topological sort. Every path ending at a vertex

v \neq = s

reaches it through some incoming edge

uv

. All such predecessors

u

occur earlier, so their finalized shortest-path distances have already been considered when

v

is processed. Taking the minimum of

distance (u) + w (u, v)

over these edges therefore gives exactly the shortest-path distance to

v

. Unreachable vertices retain infinity. Negative edge weights cause no difficulty because a later vertex cannot lead back to an earlier one.

This is the DAG shortest-path algorithm. Topological sorting and the single pass of edge relaxation each take $O (∣ V ∣ + ∣ E ∣)$ time with adjacency lists; distances, predecessors and the order use

O (∣ V ∣)

auxiliary space. Following predecessors reconstructs a shortest path to any reachable target.

 Read the full article

 New to topics? Read the docs here!