[
https://issues.apache.org/jira/browse/FLINK-4965?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17323697#comment-17323697
]
Flink Jira Bot commented on FLINK-4965:
---------------------------------------
This issue is assigned but has not received an update in 7 days so it has been
labeled "stale-assigned". If you are still working on the issue, please give an
update and remove the label. If you are no longer working on the issue, please
unassign so someone else may work on it. In 7 days the issue will be
automatically unassigned.
> AllPairsShortestPaths
> ---------------------
>
> Key: FLINK-4965
> URL: https://issues.apache.org/jira/browse/FLINK-4965
> Project: Flink
> Issue Type: New Feature
> Components: Library / Graph Processing (Gelly)
> Affects Versions: 1.2.0
> Reporter: Greg Hogan
> Assignee: Greg Hogan
> Priority: Major
> Labels: algorithm, stale-assigned
>
> 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
(v8.3.4#803005)
