Ask Your Question

Morgoth's profile - activity

2014-05-11 22:45:49 -0600 received badge  Famous Question (source)
2013-12-02 16:39:04 -0600 received badge  Notable Question (source)
2013-10-06 00:44:50 -0600 received badge  Popular Question (source)
2013-08-21 13:07:19 -0600 received badge  Self-Learner (source)
2013-08-21 13:07:19 -0600 received badge  Teacher (source)
2013-08-14 10:33:03 -0600 commented answer Finding all shortest paths between given (specific) pair of vertices

there you go :)

2013-07-26 00:50:30 -0600 commented answer Finding all shortest paths between given (specific) pair of vertices

Hello! The all_dist dictionary comes from "distance_all_pairs" method, mentioned by Nathann. If you add something like "all_dist = G.distance_all_pairs()" in the beginning, it should work. If you wish, I can publish full code here, but I would rather not, since I am not really sage master myself :)

2013-07-15 17:35:03 -0600 received badge  Nice Question (source)
2013-07-15 04:54:35 -0600 received badge  Student (source)
2013-07-15 03:07:51 -0600 answered a question Finding all shortest paths between given (specific) pair of vertices

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
2013-07-15 02:57:05 -0600 commented answer Finding all shortest paths between given (specific) pair of vertices

I do not know how to paste the code here, therefore I wrote an answer below.

2013-07-09 04:21:11 -0600 received badge  Supporter (source)
2013-07-09 04:20:39 -0600 commented answer Finding all shortest paths between given (specific) pair of vertices

Thank you, but this is too much brute force for me. Anyway, it is good to know all_paths function.

2013-07-09 04:19:48 -0600 commented answer Finding all shortest paths between given (specific) pair of vertices

That is a good approach. Little more work on my side, but it gets the job done.

2013-07-09 04:19:09 -0600 marked best answer Finding all shortest paths between given (specific) pair of vertices

You can easily find the list of all predecessors : just call the "distance_all_pairs" method, and you can then get all predecessors of x in a shortest u-v path as the list of all neighbors p of x such that d(u,p)+1+d(x,v)=d(u,v).

Nathann

2013-07-09 04:19:09 -0600 received badge  Scholar (source)
2013-07-09 00:54:50 -0600 received badge  Editor (source)
2013-07-09 00:45:53 -0600 asked a question Finding all shortest paths between given (specific) pair of vertices

I am working with graphs in sage and need a method of finding all shortest paths between some pair (or all pairs) of vertices.

Note that it is important to have all shortest paths registred, not just one, as seen in many Bellman-Ford/Dijkstra implementations (for instance Graph.shortest_path_all_pairs or networkx.algorithms.shortest_paths.all_pairs_shortest_path), and not just a number of those paths.

I am also satisfied with only a list of "optimal" predecessors... as long as the list is complete.

Thank you for answers!