You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by "Greg Hogan (JIRA)" <ji...@apache.org> on 2017/02/28 15:04:45 UTC
[jira] [Updated] (FLINK-4965) AllPairsShortestPaths
[ https://issues.apache.org/jira/browse/FLINK-4965?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Greg Hogan updated FLINK-4965:
------------------------------
Labels: Algorithm (was: )
> AllPairsShortestPaths
> ---------------------
>
> Key: FLINK-4965
> URL: https://issues.apache.org/jira/browse/FLINK-4965
> Project: Flink
> Issue Type: New Feature
> Components: Gelly
> Affects Versions: 1.2.0
> Reporter: Greg Hogan
> Assignee: Greg Hogan
> Labels: Algorithm
>
> Add a Gelly implementation of {{AllPairsShortestPaths}} to complement the existing {{SingleSourceShortestPaths}}.
> Flink algorithms excel at processing big, sparse data. APSP is big, really big, but not at all sparse. Considering only undirected graphs, each component of size {{n}} will have {{n choose 2}} shortest paths (1,000 vertices => ~million paths, 1,000,000 vertices => ~trillion shortest paths).
> Considerations are directed vs undirected and weighted vs unweighted graphs. The actual shortest path (not merely the distance) is required for follow-on algorithms such as betweenness centrality.
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)