Revision history [back]

If you are fine with exponential time in $k$, then to compute the number of $k$-paths you can employ the approach outlined in Section 4 of my paper https://arxiv.org/abs/1602.01396

def number_of_k_paths(G,s,t,k):
    V = G.vertices(sort=True)
    A = G.adjacency_matrix()
    i_s = V.index(s)
    i_t = V.index(t)
    r = 0
    for Tsize in range(k):
        for T in Subsets(Set(V) - Set({s,t}),Tsize):
            L = [i for i,v in enumerate(V) if v==s or v==t or v in T]
            r += (-1)^(k+1-len(L)) * binomial(len(V)-len(L),k+1-len(L)) * (A.matrix_from_rows_and_columns(L,L)^k)[L.index(i_s),L.index(i_t)]
    return r

For example, number_of_k_paths(graphs.AfricaMap(),'Namibia', 'Libya',5) gives 9, which is consistent with the example given by @dan_fulea.