[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