Ask Your Question
2

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

asked 2013-07-09 00:45:53 -0500

Morgoth gravatar image

updated 2013-07-09 00:54:50 -0500

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!

edit retag flag offensive close merge delete

3 answers

Sort by ยป oldest newest most voted
3

answered 2013-07-09 02:28:14 -0500

Nathann gravatar image

updated 2013-07-09 04:53:32 -0500

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

edit flag offensive delete link more

Comments

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

Morgoth gravatar imageMorgoth ( 2013-07-09 04:19:48 -0500 )edit

Would you show a minimum working example so that the answer implementation is clear(er)?

rickhg12hs gravatar imagerickhg12hs ( 2013-07-11 19:31:15 -0500 )edit

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

Morgoth gravatar imageMorgoth ( 2013-07-15 02:57:05 -0500 )edit
2

answered 2013-07-09 01:47:50 -0500

tmonteil gravatar image

updated 2013-07-09 01:51:55 -0500

There seem not to be an existing method in Sage for doing that out of the box, so you should write your own algorithm. If you are lazy, you can still use the following slow brute force method, depending on the size of your graph:

sage: G = graphs.GrotzschGraph()
sage: allp = G.all_paths(1,4)
sage: m = min(len(p) for p in allp) ; m
3
sage: [p for p in allp if len(p) == m]
[[1, 0, 4], [1, 10, 4]]
edit flag offensive delete link more

Comments

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

Morgoth gravatar imageMorgoth ( 2013-07-09 04:20:39 -0500 )edit
1

answered 2013-07-15 03:07:51 -0500

Morgoth gravatar image

updated 2015-10-15 03:42:40 -0500

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
edit flag offensive delete link more

Comments

Sorry, I'm a graph theory noob. Where does all_dist come from? [The above snippet crashes.]

rickhg12hs gravatar imagerickhg12hs ( 2013-07-15 17:27:43 -0500 )edit

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 :)

Morgoth gravatar imageMorgoth ( 2013-07-26 00:50:30 -0500 )edit

Defining all_dist as above isn't quite enough to make the code work (still crashes). Wish @Nathann would post a complete minimum working example (MWE). Perhaps @tmonteil would be kind enough to provide a MWE for the method of @Nathann.

rickhg12hs gravatar imagerickhg12hs ( 2013-07-26 09:22:56 -0500 )edit
1

there you go :)

Morgoth gravatar imageMorgoth ( 2013-08-14 10:33:03 -0500 )edit

Took me a while to see that this produces the shortest path for all pairs. Nice!

rickhg12hs gravatar imagerickhg12hs ( 2013-08-21 13:07:08 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-07-09 00:45:53 -0500

Seen: 1,925 times

Last updated: Oct 15 '15