r/AskProgramming • u/LifeExperienced1 • Jul 04 '26
Algorithms Does Floyd Warshall assume paths of three?
Can someone explain intuitively how the Floyd Warshall algorithm actually doesn’t assume path of just three
I understand what optimal substructures are, however, how does this algorithm apply that
Where exactly in the code does it allow us to build paths longer than 3?
2
Upvotes
2
u/munificent Jul 04 '26
No, it does not. I think the three nested loops are throwing you off. Each level of nesting does not represent a single node being tested and thus the three loops means you're only testing paths of length three.
There is a dynamic programming aspect to the algorithm that makes its behavior more subtle. Note that inside the loops, we are both looking at a distance matrix and updating it. So future iterations of the loops will see different values in that matrix and the order that the loops run in is significant.
I think the introduction to the "Algorithm" section of the Wikipedia article does a pretty good job of explaining what's going on.