## 12.4 Serial Polyadic DP FormulationsFloyd's algorithm for determining the shortest paths between all pairs of nodes in a graph can be reformulated as a serial polyadic DP formulation. ## 12.4.1 Floyd's All-Pairs Shortest-Paths AlgorithmConsider a weighted graph G, which consists of a set of nodes V and a set of edges E. An edge from node i to node j in E has a weight c Let be the minimum cost of a path from node i to node j, using only nodes v Since is the shortest path from node i to node j using all n nodes, it is also the cost of the overall shortest path between nodes i and j . The sequential formulation of this algorithm requires n iterations, and each iteration requires time Q(n Equation 12.6 is a serial polyadic formulation. Nodes can be partitioned into n levels, one for each value of k. Elements at level k + 1 depend only on elements at level k. Hence, the formulation is serial. The formulation is polyadic since one of the solutions to requires a composition of solutions to two subproblems and from the previous level. Furthermore, the dependencies between levels are sparse because the computation of each element in requires only three results from the preceding level (out of n A simple CREW PRAM formulation of this algorithm uses n As with serial monadic formulations, data locality is of prime importance in serial polyadic formulations since many such formulations have sparse connectivity between levels. |