Finding all shortest paths between given (specific) pair of vertices

savecancel

The method, suggested by Nathann is the following:

 for v in G.vertices():
    for u in G.vertices():
        predec_list[u][v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1]

Given such list (p_l), it is easy to recursively construct a list of shortest paths from vertex a to vertex b, as follows:

def s_p_d(p_l,a,b):
    r=[]
    if p_l[a,b]==[a]:
        r.append([a,b])
    else:
        for i in p_l[a,b]:
            for j in s_p_d(p_l,a,i):
                j.append(b)
                r.append(j)
    return r

rickhg12hs: here is my code snippet. This works for me :) Make sure to have networkx imported.

def list_of_predecessors(G):
    all_dist=G.distance_all_pairs()
    predec_list= {}
    for v in G.vertices():
        for u in G.vertices():
            predec_list[u,v]=[i for i in G.neighbors(v) if all_dist[u][i]==all_dist[u][v]-1] 
    return predec_list


def shortest_path_d(G):
    a_p= { "init":0}
    p_l = list_of_predecessors(G)
    for u in G.vertices():
        for v in G.vertices():
            a_p[(u,v)]=s_p_d(p_l,u,v)
    del a_p["init"]
    return a_p

def s_p_d(p_l,a,b):
    r=[]
    if p_l[a,b]==[a]:
        r.append([a,b])
    else:
        for i in p_l[a,b]:
            for j in s_p_d(p_l,a,i):
                j.append(b)
                r.append(j)
    return r