The Shortest Path in an Unweighted Graph

Three things an answer should state about that output. Unreachable is a real answer, and the algorithm must report it rather than return a wrong number or loop. The first arrival is the shortest, which is why the test is if w not in distance and no distance is ever revised. And the route is rebuilt from the parents, so a shortest path costs no extra traversal.

Why DFS cannot be used here

def adjacency(pairs, vertices):
    graph = {v: [] for v in vertices}
    for a, b in pairs:
        graph[a].append(b)
        graph[b].append(a)
    for v in graph:
        graph[v].sort()
    return graph


EDGES = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"),
         ("C", "E"), ("D", "F"), ("E", "F"), ("F", "G")]
GRAPH = adjacency(EDGES, "ABCDEFG")


def dfs_first_arrival(graph, v, depth=0, seen=None, found=None):
    """DFS, recording the depth at which each vertex is FIRST reached."""
    if seen is None:
        seen, found = set(), {}
    seen.add(v)
    found[v] = depth
    for w in graph[v]:
        if w not in seen:
            dfs_first_arrival(graph, w, depth + 1, seen, found)
    return found


from collections import deque


def bfs_distance(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in distance:
                distance[w] = distance[v] + 1
                queue.append(w)
    return distance


dfs_depth = dfs_first_arrival(GRAPH, "A")
bfs_dist = bfs_distance(GRAPH, "A")

print("%-8s %12s %12s %s" % ("vertex", "DFS depth", "BFS distance", "DFS wrong by"))
wrong = 0
for v in sorted(GRAPH):
    gap = dfs_depth[v] - bfs_dist[v]
    if gap:
        wrong += 1
    print("%-8s %12d %12d %s"
          % (v, dfs_depth[v], bfs_dist[v], gap if gap else ""))

print()
print("DFS overstated the distance for", wrong, "of", len(GRAPH), "vertices.")
print("DFS commits to a branch before checking a shorter one exists.")
print("the BFS numbers are the true shortest distances.")

vertex      DFS depth BFS distance DFS wrong by
A                   0            0
B                   1            1
C                   3            1 2
D                   2            2
E                   4            2 2
F                   5            3 2
G                   6            4 2

DFS overstated the distance for 4 of 7 vertices.
DFS commits to a branch before checking a shorter one exists.
the BFS numbers are the true shortest distances.

DFS is not wrong about reachability; it is wrong about distance. It walks into a long branch and records the depth it happened to arrive at, with no reason for that to be minimal.

The trap: an unweighted algorithm on a weighted graph

This is the examinable mistake, and the reason the next chapter exists.

from collections import deque

# A weighted graph. BFS cannot see the weights at all.
WEIGHTED = {
    "A": [("B", 1), ("C", 10)],
    "B": [("A", 1), ("D", 20)],
    "C": [("A", 10), ("D", 1)],
    "D": [("B", 20), ("C", 1)],
}

print("the weighted graph:")
for v in sorted(WEIGHTED):
    print("   %s -> %s" % (v, ", ".join("%s(%d)" % p for p in WEIGHTED[v])))
print()

# BFS: fewest EDGES from A to D
distance, parent = {"A": 0}, {"A": None}
queue = deque(["A"])
while queue:
    v = queue.popleft()
    for w, _weight in WEIGHTED[v]:
        if w not in distance:
            distance[w] = distance[v] + 1
            parent[w] = v
            queue.append(w)

bfs_route = []
node = "D"
while node is not None:
    bfs_route.append(node)
    node = parent[node]
bfs_route.reverse()


def cost(route):
    total = 0
    for a, b in zip(route, route[1:]):
        total += next(w for n, w in WEIGHTED[a] if n == b)
    return total


print("BFS answer    :", " -> ".join(bfs_route),
      "  edges:", len(bfs_route) - 1, "  cost:", cost(bfs_route))
better = ["A", "C", "D"]
print("a cheaper route:", " -> ".join(better),
      "  edges:", len(better) - 1, "  cost:", cost(better))
print()
print("BFS picked the route with fewer edges and it costs more:",
      cost(bfs_route) > cost(better))
print("it is worse by", cost(bfs_route) - cost(better), "units.")
print()
print("BFS answers 'fewest edges'. on a weighted graph that is a different")
print("question from 'cheapest', so BFS is the wrong tool: use Dijkstra.")

the weighted graph:
   A -> B(1), C(10)
   B -> A(1), D(20)
   C -> A(10), D(1)
   D -> B(20), C(1)

BFS answer    : A -> B -> D   edges: 2   cost: 21
a cheaper route: A -> C -> D   edges: 2   cost: 11

BFS picked the route with fewer edges and it costs more: True
it is worse by 10 units.

BFS answers 'fewest edges'. on a weighted graph that is a different
question from 'cheapest', so BFS is the wrong tool: use Dijkstra.

Both routes are two edges long, so BFS has no way to prefer either and takes whichever its neighbour order reaches first. BFS is not approximately right on a weighted graph. It is answering a different question.

Which algorithm for which problem

The row to remember for an examination is the second one: when every weight is the same, BFS is the correct and faster answer, and reaching for Dijkstra shows the distinction was missed.

Cost

Exactly the BFS cost, since it is BFS: O(V + E) time on an adjacency list, O(V) extra space for the distance and parent maps. Dijkstra is O((V + E) log V), so on an unweighted graph BFS is not only correct but strictly cheaper.

Quick revision

• When all edges cost the same, shortest means fewest edges, and BFS already solves it.
• The proof: BFS reaches level k only after level k-1 is finished, so a first arrival cannot be beaten.
• Record a parent on first arrival; the parents chain back to give the route.
• A distance is never revised, which is why the test is "not yet seen".
• Unreachable must be reported as unreachable, not as a number.
• DFS gives wrong distances because it commits to a branch before checking for a shorter route.
• On a weighted graph BFS answers the wrong question: it chose a 2 edge route costing 21 over a 2 edge route costing 11.
• BFS here is O(V + E), cheaper than Dijkstra's O((V + E) log V), so do not use Dijkstra on an unweighted graph.

Test yourself

1. Why does BFS give the shortest path in an unweighted graph? Because it processes all vertices at level k-1 before any at level k, so a vertex first reached at level k has no shorter route; one would have reached it on an earlier level.

2. How is the route itself recovered? By recording, for each vertex, the vertex it was first reached from, then following those parents back from the target to the start and reversing.

3. Why is a distance never updated once set? Because the first arrival is already the shortest, so any later arrival is at least as long.

4. Why can DFS not be used for shortest paths? It follows one branch to its end before trying another, so the depth at which it first reaches a vertex is whatever that branch gave, not the minimum.

5. What happens if BFS is used on a weighted graph? It returns the route with the fewest edges, which is a different question. In the chapter's example it chose a route costing 21 over one costing 11, both two edges long.

6. The graph is weighted but every weight is 5. Which algorithm? BFS. All weights being equal makes cheapest the same as fewest edges, and BFS is O(V + E) against Dijkstra's O((V + E) log V).

7. How must an unreachable vertex be reported? As unreachable, with no distance. It must never be given a number or cause the algorithm to loop.