Re: [igraph] Complexity time

[Gábor Csárdi]

As for Johnson's algorithm, I am not sure why it is not in the C docs,
but here is the time complexity from the code:

[...]
 * Time complexity: O(s|V|log|V|+|V||E|), |V| and |E| are the number
 * of vertices and edges, s is the number of source vertices.
[...]

G.

On Tue, Dec 7, 2010 at 3:40 PM, Romildo Martins
<address@hidden> wrote:
> Hello,
>
> View Johnson Algorithm in
> http://igraph.sourceforge.net/doc/R/shortest.paths.html
>
> Thanks a lot!
>
> 2010/12/6 Tamas Nepusz <address@hidden>:
>> Hello,
>>
>>> What complexity time of implemented algorithm (dijkstra, bellman-ford
>>> and johnson)?
>> You can find the time complexities of the first two in the manual:
>>
>> http://cneurocvs.rmki.kfki.hu/igraph/doc/html/igraph_shortest_paths_dijkstra.html
>> http://cneurocvs.rmki.kfki.hu/igraph/doc/html/igraph_shortest_paths_bellman_ford.html
>>
>> Johnson's algorithm is not implemented in igraph 0.5.4 as far as I know.
>>
>> --
>> Tamas
>>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM