Tag: dynamic-programming

Floyd-Warshall turned all-pairs shortest paths into a compact dynamic program: allow intermediate vertices one by one and update a distance matrix in cubic time.

Richard Bellman turned multistage decision problems into a recursive method in which later optimal choices are reused to solve earlier ones, creating dynamic programming as a general algorithmic strategy.