[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Complexity time
From: |
Tamas Nepusz |
Subject: |
Re: [igraph] Complexity time |
Date: |
Tue, 7 Dec 2010 14:45:13 +0000 |
User-agent: |
Mutt/1.5.20 (2009-06-14) |
Hello,
> View Johnson Algorithm in
> http://igraph.sourceforge.net/doc/R/shortest.paths.html
Whoops, looks like Johnson's algorithm is missing from the online
documentation of the C core then. Thanks for pointing that out!
Anyways, the time complexity of Johnson's algorithm is O(s |V| log|V| +
|V| |E|), where s is the number of source vertices, |V| and |E| are the
number of vertices and edges.
--
Tamas