# Revision history [back]

The method, suggested by 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


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


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. Lines 3 and 7 are probably obsolate. I use them just to initialize the dictionary predec_list, and clean up the mess in the end.

def list_of_predecessors(G):
all_dist=G.distance_all_pairs()
predec_list= { "init":0}
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]
del predec_list["init"]
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


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. Lines 3 and 7 are probably obsolate. I use them just to initialize the dictionary predec_list, and clean up the mess in the end.

def list_of_predecessors(G):
all_dist=G.distance_all_pairs()
predec_list= { "init":0}
{}
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]
del predec_list["init"]
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