[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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
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
pgpBTvTJEmQcK.pgp
Description: PGP signature