Greg Hogan created FLINK-4965:
---------------------------------
Summary: 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
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.4#6332)
