[Networkit] All pairs shortest path

Elisabetta Bergamini elisabetta.bergamini at kit.edu
Tue Dec 13 14:04:13 CET 2016


HI Christian,

what are your running time requirements?
I tried to generate a random weighted graph with 1000 nodes and about 500K edges and APSP took seconds on my laptop.
Would that work for you? There are no heuristics for approximating shortest paths distances in NetworKit at the moment. However, a very simple one could be to just select a set L of central nodes (e.g. node with highest degree or high approx. betweenness), compute a SSSP from each of them and approximate the distance between any two nodes (u, v) as min_{l in L} d(u, l) + d(l, v).
Best,

Elisabetta

==========================================================
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Elisabetta Bergamini
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41821
Web: http://parco.iti.kit.edu/bergamini

KIT - The Research University in the Helmholtz Association
==========================================================

On Dec 13, 2016, at 12:04, Christian Staudt <christian.staudt at kit.edu> wrote:

> 
>> On 13 Dec 2016, at 10:27, Henning Meyerhenke <henning.meyerhenke at kit.edu> wrote:
>> 
>> Will the APSP problem be executed once or do they want to make repeated
>> queries? What is the exact output required, (an estimate of) the full
>> distance matrix?
>> 
>> There is some support for APSP, but I doubt something matching your
>> scenario. But to judge that some more detail is required. In particular,
>> the input/output specifications (also in terms of size and expected
>> practical running time) will exclude certain algorithms.
> 
> On a dense weighted network of about 1000 nodes, APSP should be run once.
> 
> 
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20161213/3252d669/attachment.html>


More information about the NetworKit mailing list