[Networkit] All pairs shortest path

Henning Meyerhenke henning.meyerhenke at kit.edu
Tue Dec 13 09:27:31 CET 2016


Hi Christian,


Am 13.12.16 um 06:14 schrieb Christian Staudt:
> Hi NetworKit community,
> 
> it so happens that I have a client who wants to solve an all-pairs shortest path problem on dense weighted graphs, and the question is whether I can recommend NetworKit. Here are a couple of issues I had:
> 
> - The FloydWarshall algorithm does not exist on the Python layer
> -  What is the intended class hierarchy for APSP algorithms? class APSP inherits from APAPP<edgeweight> - but what is APAPP and where is APAPP.h ?
> - I would have expected these algorithms in the networkit/distance module. Instead they are in the networkit/graph folder (which reminds me a bit of a PhD student’s desk on the day before the deadline*).
> 
> Because FloydWarshall will not scale, and no exact algorithm would, do you know any methods to get an estimate of the distances for this scenario (weighted, dense graph)? Has any work in this direction been done within NetworKit?

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.

Best,
Henning

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20161213/7579645c/attachment.p7s>


More information about the NetworKit mailing list