Re: [igraph] shortest path between two vertices

[Tamas Nepusz]

Hi Benjamin,

If you only need a single path and not all of it,  
igraph.Graph.get_shortest_paths() is your friend. I.e.:

g = Graph.Full(10)
g.es["weight"] = range(45)
g.get_shortest_paths(1, "weight")

--
T.

On 2009.05.16., at 16:24, Benjamin Fields wrote:

> Is there any way to get the actual path (ie. list of vertices) back  
> (not just the path length)  for a weighted graph in the python  
> interface?  I know I can get the paths via  
> igraph.Graph.get_all_shortest_paths() for an unweighted graph, but  
> there doesn't seem to be anyway to specify an edge attribute to use  
> as weight.  Basically if igraph.Graph.shortest_paths() actually  
> returned the path and not the length I'd be set.  Any suggestions?
>
> cheers
>
> Ben
>
>
>
> Benjamin Fields
> PhD Candidate
> Dept. of Computing
> Goldsmiths, University of London
> address@hidden
> mobile: +44 (0)796 106 1568
> "Which is more musical: a truck passing by a factory or a truck  
> passing by a music school?" --John Cage
>
>
>
>
>
>
>
>
>
>
> On Feb 3, 2009, at 2:53 AM, Chris Wj wrote:
>
> > Hmm, I'm using development main branch 0.6 and this worked for me:
> > print g.shortest_paths( source=[0], target=[1], weights=None,  
> > mode=igraph.ALL)
> >
> > The docs from 0.5.1 (http://cneurocvs.rmki.kfki.hu/igraph/doc/python/index.html 
> > ) say:
> >
> > shortest_paths_dijkstra(vertices, weights=None, mode=OUT)
> > Calculates shortest path lengths for given nodes in a graph.
> > Parameters:
> > vertices - a list containing the vertex IDs which should be  
> > included in the result.
> > weights - a list containing the edge weights. It can also be an  
> > attribute name (edge weights are retrieved from the given  
> > attribute) or None (all edges have equal weight). Edge weights must  
> > be non-negative for the algorithm to work (since weighted shortest  
> > path calculation is based on Dijkstra's algorithm)
> > mode - the type of shortest paths to be used for the calculation in  
> > directed graphs. OUT means only outgoing, IN means only incoming  
> > paths. ALL means to consider the directed graph as an undirected one.
> >
> > Returns:the shortest path lengths for given nodes in a matrix
> >
> >
> >
> > On Mon, Feb 2, 2009 at 9:33 PM, Rajarshi Guha <address@hidden>  
> > wrote:
> >
> >
> > On Mon, Feb 2, 2009 at 9:01 PM, Chris Wj <address@hidden> wrote:
> > From source doc:
> >
> > shortest_paths(source=None, target=None, weights=None, mode=OUT)
> >
> >
> > import igraph
> > G = igraph.Graph()
> > # create your graph
> > spaths_from_0 = G.shortest_paths(0)
> >
> > Thanks for the pointer. But igraph 0.5.1 and Python 2.5 the  
> > following code gives an error
> >
> > print g.shortest_paths( source=[0], targets=[1], weights=None,  
> > mode=igraph.ALL)
> >
> > Traceback (most recent call last):
> >  File "goanal.py", line 61, in <module>
> >    print g.shortest_paths( source=[0], targets=[1])
> > TypeError: 'source' is an invalid keyword argument for this function
> >
> >
> >
> >
> > --
> > Rajarshi Guha
> >
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden
> > http://lists.nongnu.org/mailman/listinfo/igraph-help
> >
> >
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden
> > http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help