SPA - Best way of implementation

[Jeff Epler]

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
            queue.append(next_partial)

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

Jeff
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20040605/a2b52297/attachment.sig>