Floyd Warshall's All pair shortest path problem does not evaluate all possible paths We know that the FW all pair shortest path is a Dynamic Programming (DP) approach to solving the problem. Being a DP, it smartly evaluates all possible options before deciding the final option at each stage.

I have manually evaluated and traced a 5 node graph with this algorithm. The actual graph is not important here. I will take the example of the evaluation of path(V4,V5) in iteration 1 and 2 only:

Stage 1: min{(4,5),(4,1,5)} of Stage 0 

Stage 2: min{(4,5), (4,2,5)} of Stage 1

So if we expand this, then by the end of Stage 2, we have actually essentially evaluated the paths {(4,5) , (4,1,5), (4,2,5), (4,2,1,5), (4,1,2,1,5)} and selected the minimum.

As seen, we are evaluating cyclic paths as well e.g. (4,1,2,1,5) from above. If we continue tracing the algorithm till the end, we find that we never evaluate the path (4,2,1,2,5) for this specific example. Does this mean, not all paths are evaluated with this algorithm? I know not evaluating it won't harm as it will definitely not be the shortest path but my point is that should have been the case with (4,1,2,1,5) too. It looks like although the output is correct and consistent, yet theoretically speaking certain paths are not evaluated because of the way the algorithm is structured and not out of merit. Am I missing something here?
Yes, the path $(4,2,1,2,5)$ is not evaluated.
However this is not a problem.

Since we assume that the graph doesn't contain any negative cycles (this is a requirement for FW), there exists an optimal path for each pair of nodes that doesn't contain any cycles.
Therefore the algorithm only needs to guarantee, that cycle-less path gets evaluated.

By induction you can show that this is always the case.
Let $k$ be the variable in the most outer loop.
Induction hypothesis: After the $k$th iteration the table contains all the shortest paths between each pair that only uses nodes $\le k$ on the path (without start and end node).

At the beginning this is trivially true.
And also the induction step, going from $k$ to $k+1$, is pretty easy to show:
A minimal path using only nodes $\le k + 1$ from $u$ to $v$ either contains only nodes $\le k$, or it contains a minimal path from $u$ to $k+1$ combined with the minimal path from $k+1$ to $v$. (Here we use the fact that the paths contain no cycles. If a path contains cycles, this statement ca be wrong.)
And exactly this case is handled in the algorithms.

Therefore at the end the table contains all minimal paths.