SPA - Best way of implementation

Jeff Epler jepler at
Sat Jun 5 17:05:46 CEST 2004

Here's an algorithm to find the shortest path from start to end.  It is
not Dijkstra's "single source shortest paths" algorithm, and that a
crucial step of the BFS is O(|queue|) instead of O(1).

def shortest_path(start, end, adj):
    seen = {start: None}       # XXX use sets here instead
    queue = [[start]]
    while queue:
        partial = queue.pop(0) # XXX this is O(|queue|)
        tail = partial[-1]
        for edge in adj[tail]:
            if edge in seen: continue
            seen[edge] = None
            next_partial = partial + [edge]
            if edge == end:
                return next_partial

>>> edges = {'A': 'K', 'K': 'R', 'R': 'BC', 'B': 'I', 'I': 'C'}
>>> "".join(mallek.shortest_path('A', 'C', edges))

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <>

More information about the Python-list mailing list