igraph-help
[Top][All Lists]

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

 From: Tamas Nepusz Subject: Re: [igraph] Floyd-Warshall or other all-pairs-shortest paths in igraph? Date: Wed, 10 Jun 2009 12:09:16 +0100 User-agent: Mutt/1.5.17 (2007-11-01)

```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
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"
> 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