Thanks @jacob.small and @Vikram_Subbaiah,
Finally found a solution that takes all shortest paths and counts the least number bending,
Thanks to the Source code of NetworkX package.
#Thanks to NetworkX`
keys=IN[0]
values=IN[1]
G = dict(zip(keys,values))
source=IN[2]
target=IN[3]
path=[]
def predecessor(G,source,target=None,cutoff=None,return_seen=None):
level=0 # the current level
nextlevel=[source] # list of nodes to check at next level
seen={source:level} # level (number of hops) when seen in BFS
pred={source:[]} # predecessor dictionary
while nextlevel:
level=level+1
thislevel=nextlevel
nextlevel=[]
for v in thislevel:
for w in G[v]:
if w not in seen:
pred[w]=[v]
seen[w]=level
nextlevel.append(w)
elif (seen[w]==level):# add v to predecessor list if it
pred[w].append(v) # is at the correct level
if (cutoff and cutoff <= level):
break
if target is not None:
if return_seen:
if not target in pred: return ([],-1) # No predecessor
return (pred[target],seen[target])
else:
if not target in pred: return [] # No predecessor
return pred[target]
else:
if return_seen:
return (pred,seen)
else:
return pred
def all_shortest_paths(G, source, target, weight=None, method='dijkstra'):
method = 'unweighted' if weight is None else method
if method == 'unweighted':
pred = predecessor(G, source)
else:
raise ValueError('method not supported: {}'.format(method))
if target not in pred:
raise ValueError('Target {} cannot be reached'
'from Source {}'.format(target, source))
stack = [[target, 0]]
top = 0
while top >= 0:
node, i = stack[top]
if node == source:
yield [p for p, n in reversed(stack[:top + 1])]
if len(pred[node]) > i:
top += 1
if top == len(stack):
stack.append([pred[node][i], 0])
else:
stack[top] = [pred[node][i], 0]
else:
stack[top - 1][1] += 1
top -= 1
OUT=all_shortest_paths(G, source, target, weight=None, method='dijkstra')
graph here : core version_0.3.dyn (183.9 KB)
