Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 5 / d / Solution 2026-10-31
View more
Use minimum-hop shortest paths by minimizing the lexicographic order pair : total weight first, number of edges second. Extend a pair across an edge of weight by adding , and compare the full pair in both the priority queue and relaxation:
for v in V: key[v] = (infinity,infinity)
key[s] = (0,0)
Q = indexed min-priority-queue containing all vertices, keyed by key
while Q is not empty:
    u = extract-min(Q)
    if key[u].distance == infinity: break
    for each edge (u,v) of weight w with v still in Q:
        candidate = (key[u].distance + w, key[u].hops + 1)
        if candidate <lex key[v]:
            key[v] = candidate
            decrease-key(Q,v,candidate)
for v in V: best[v] = key[v].hops
All weights are positive, so extending a path strictly increases its first component. The usual Dijkstra's algorithm settled-label proof therefore applies to these ordered pairs: no path through a not-yet-settled vertex can later improve an extracted minimum. Among equal minimum weights, the secondary component selects the fewest edges. Merely breaking extraction ties by vertex name would not implement this objective.
With a binary heap and adjacency lists, the bound is , with extra storage. Unreachable vertices have best = infinity. In the paper's example, the resulting pairs in order are , so the requested edge counts are .
Read the full article