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


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


>>> 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.


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

Attachment: pgpBTvTJEmQcK.pgp
Description: PGP signature

reply via email to

[Prev in Thread] Current Thread [Next in Thread]