
%\noindent \textbf{Graph Algorithm - All-pairs shortest Path}
\subsection{Graph Algorithm - All-pairs shortest Path}

\lstset{language=C++}
\begin{lstlisting}
#include "prelude.cpp"

void floyd(vector<edge>& edgepairs,
            map<edge, weight>& weights,
            map<edge, weight>& spath,
            map<edge, vector<edge> >& path,
            int n) {
  weight MAX_PATH = 999999;
  FOR(k,n) {
      FOR(i,n) {
          spath[edge(i,k)] = MAX_PATH;
      }
  }

  FOREACH(it, edgepairs) {
      spath[*it] = weights[*it];
      path[*it].push_back( *it );
  }

  FOR(k,n) {
    FOR(i,n) {
      FOR(j,n) {
        edge ij = edge(i,j);
        edge ik = edge(i,k);
        edge kj = edge(k,j);
        int w = spath[ik] + spath[kj];
        if( w < spath[ij] ) {
           // record path weight info
          spath[ij] = w;
          // also record actual path info
          path[ij].clear();
          path[ij].insert(path[ij].end(),
                           ALL(path[ik]));
          path[ij].insert(path[ij].end(),
                           ALL(path[kj]));
        }
      }
    }
  }
}
\end{lstlisting}
\normalsize

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "../ref-doc"
%%% End:
