Algorithms - Parallel version of Floyd-Warshall Pseudocode. Floyd-Warshall (W) n

Question

Algorithms - Parallel version of Floyd-Warshall Pseudocode.

Floyd-Warshall (W) n = W.rows create n x n array D for i = 1 to n for j = 1 to n D[i, j] = W[i, j] for k = 1 to n for i = 1 to n for j = 1 to n D[i, j] = min(D[i, j], D[i, k] + D[k, j]) return D Design a parallel version of this algorithm using spawn, sync. and/or parallel for as appropriate. (Copy and modify the pseudocode.) Think carefully about what can be parallelized and what can't, and explain your choices. Analyze the asymptotic runtime of your algorithm in terms of its work, span, and parallelism asymptotic runtime of your algorithm in terms of its work, span, and parallelism

Explanation / Answer

FLOYD-WARSHALL(W) 1. n = W.rows 2. D(0) = W 3. (0) = (0)ij = NIL if i=j or wij = = i if ij and wij < 4. for k = 1 to n 5. let D(k) = (d(k)ij) be a new nxn matrix 6. for i = 1 to n 7. for j = 1 to n 8. dkij = min(d(k-1)ij, d(k-1)ik + d(k-1)kj) 9. if d(k-1)ij d(k-1)ik + d(k-1)kj 10. (k)ij = (k-1)ij 11. else 12. (k)ij = (k-1)kj 13. return D(n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---