Github user njayaram2 commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/140#discussion_r121803411
--- Diff: doc/design/modules/graph.tex ---
@@ -273,6 +274,91 @@ \subsection{Implementation Details}
Please note that, for ideal performance, \emph{vertex} and \emph{edge}
tables
should be distributed on \emph{vertex id} and \emph{source id}
respectively.
+\section{All Pairs Shortest Paths} \label{sec:graph:apsp}
+
+Given a graph and a source vertex, all pairs shortest paths (APSP)
algorithm
+finds a path for every vertex pair such that the sum of the weights of its
+constituent edges is minimized. Please refer to the
+Section~\ref{sec:graph:sssp} on single source shortest path for the
+mathematical definition of shortest path.
+
+Our implementation is based on the matrix multiplication inspired APSP
+algorithm \cite{apsp}. The idea is similar to the one from SSSP
+implementation. We start with a naive approximation for the cost of every
--- End diff --
This is actually a dynamic programming approach, you might want to mention
that along with what you have here.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---
