SPA - Best way of implementation

[Andreas Mallek]

hello,

i'm looking for a good method to create an short
path algorithm like dijkstra. well.. i hope that
i can find someone that already integrated spa's
with python.

my goal is to find ways from contact-person A to
contact-person B. but i have to save and sort
all the possible ways in a depth of about nine
max hops like this:

user A knows user K
user K knows user R
user R knows user B and C
user B knows user I
user I knows user C

now i'm looking for a way from a to c:

A -> K -> R -> C
or
A -> K -> R -> B -> I -> C


target usage:

<< FROM = 'A'
<< TO = 'C'
<< MAXHOPS = 9
<< ways = []
<< ways = find(FROM,TO,MAXHOPS)
<< print ways

[{'A','K','R','C'},{'A','K','R','B','I','C'}]

so guys.. any ideas for a short, fast and
"simple" implementation with about 20 lines of code?

greetings
andy

 

[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)
'AKRC'

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAweFJJd01MZaTXX0RAsMcAJ0RaVgTZLX1BY81ETtenNqcsx6tdwCeJ2qI
Ar2qtU3D1BI/eNuCajeYUuY=
=h3ez
-----END PGP SIGNATURE-----