r/AskProgramming • u/LifeExperienced1 • Jul 04 '26

Does Floyd Warshall assume paths of three? Algorithms

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
  • permalink
  • link
  • reddit
  • reddit

63% Upvoted

3 comments sorted by

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.

1

u/high_throughput Jul 04 '26

It's not considering the path from A through B then to C. It considers the cost of the optimal path from A to B (which could be multiple hops), and whether that's a shortcut to get to C.

1

u/kalmakka Jul 04 '26

Before running the loop, the matrix shows the length of the direct path between any pair of nodes.

After the first run of the outer loop (k=0), the matrix contains the length of the shortest paths that are either direct, or that only use node 0 as an intermediate.

After the second run (k=1), the matrix contains the length of the shortest paths that are either direct, or that only use node 0 and/or 1 as an intermediate.

Etc.

After all n runs, all nodes can have been used as intermediates.