[
https://issues.apache.org/jira/browse/MADLIB-1072?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15999095#comment-15999095
]
Frank McQuillan commented on MADLIB-1072:
-----------------------------------------
This JIRA is for a basic first implementation: Later we could look at adding
more parameters to (optionally) keep run-time/memory tractable:
* limit the number of target nodes
* limit max distance between source and destination
* switch for directed/undirected
* incremental algos for APSP on sub-graph that has been changed/affected
compared to previous graph state
* approximate techniques
> Graph - all pairs shortest path
> -------------------------------
>
> Key: MADLIB-1072
> URL: https://issues.apache.org/jira/browse/MADLIB-1072
> Project: Apache MADlib
> Issue Type: New Feature
> Components: Module: Graph
> Reporter: Frank McQuillan
> Fix For: v1.12
>
>
> Story
> As a MADlib developer, I want to implement all pairs shortest path in an
> efficient and scaleable manner.
> Acceptance
> 1) Interface defined
> 2) Design document updated
> 3) Documentation and on-line help
> 4) IC and functional tests
> 5) Scale tests
> Refs
> [1] Floyd-Warshall is one possible implemention
> https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
> [2] All-Pairs Shortest Paths with Real Weights in O(n3/ logn) Time
> https://pdfs.semanticscholar.org/82fc/17e993f4bca9efd468b5087d9d02c8ca5f6d.pdf
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)
