Design and analysis of algorithms

#1

The floyd-warshall algorithm for all pair shortest path problem is based on ______________ paradigm.

#2

Floyd Warshall Algorithm is a Dynamic Programming based algorithm.
It finds all pairs shortest paths using recursion.

For every pair (a, b) of source and destination, there are two possible cases.

  1. c is not an intermediate vertex in shortest path from a to b. We keep the value of dist[a][b] as it is.
  2. c is an intermediate vertex in shortest path from a to b. We update the value of dist[a][b] as dist[a][c] + dist[c][b].