I'm reading this.
$\quad$
He gives a proof of Floyd-Warshall's algorithm but I don't understand what he's doing nor why it proves that. I can see an intuitive proof in my mind that is as follows:
- Take one vertex, as the algorithm chooses the outgoing edge with minimum weight and goes to it, if there are edges from $A$ to $B$, then due to the algorithm's nature (picking the edge with minimum weight), this is the shortest path with minimum weight.
I don't know if it's right. I know the proof given is by induction, I just don't really know why induction is necessary in here.
After a quick glance of the linked doc: It seems that the author wants to teach dynamic programming. The approach involves a recursive solution which is then likely to be optimised with memoisation techniques (reuse of once calculated results).
Induction is a natural choice for proving a recursive method, because of its related structure (inductive step = recursion step, induction base case = recursion stop case).