Re: [igraph] Floyd-Warshall or other all-pairs-shortest paths inigraph?

[Rajorshi Biswas]

 Hi Tamas, 
Thats just what I need, thanks a lot !

Raj
http://www.rajorshi.net/blog

---------- Original message ----------
From:Tamas Nepusz< address@hidden >
Date: 10 Jun 09 16:39:16
Subject: Re: [igraph] Floyd-Warshall or other all-pairs-shortest paths inigraph?
To: Rajorshi Biswas , Help for igraph users

Hi,

Johnson's algorithm is more efficient if the input graph is sparse,
that's why we didn't implement Floyd-Warshall so far. Johnson's
algorithm in igraph has a theoretical complexity of O(s * N * log N + N
* M), where s is the number of source vertices for the shortest
path algorithm (so this is N in your case), N is the number of vertices in
the graph and M is the number of edges. This is O(N^2 * log N + N * M)
in your case. The Floyd-Warshall algorithm is O(N^3). When M << N^2,
you're better off with Johnson's algorithm. In Python, the actual
implementation of Johnson's algorithm is not exposed directly, but
Graph.shortest_paths will call it when appropriate. So you can simply
load your graph, call Graph.shortest_paths() and get the length of the
shortest path between any two vertices in a matrix. I'm assuming that
you don't need the paths themselves, as you won't get them either with
Floyd-Warshall.

Example:

>>> from igraph import *
>>> from time import time
>>> g = Graph.Barabasi(10000, 2, directed=False)
>>> start = time(); result = g.shortest_paths(); end = time()
>>> print "Calculation took %.4fs seconds" % (end - start)
Calculation took 12.4745 seconds

The result is a 10000 x 10000 matrix here.

--
Tamas


n Wed, Jun 10, 2009 at 04:09:32PM +0530, Rajorshi Biswas wrote:
> Hi, I'm trying out igraph for a project. While I see several shortest path implementations, I don't see a direct "all pairs shortest paths" implementation. Perhaps I'm missing something.Was this left out intentionally, or, as is more likely, what is the obvious thing that I'm missing :) ? If it matters, I'm using the python wrapper to igraph.Thanks in advance!~RajRajhttp://www.rajorshi.net/blogDear igraphhelp! Get Yourself a cool, short @in.com Email ID now!

> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help