动态规划是解决优化问题的一种算法策略，它将一个问题分解成相互依赖的子问题，通过解决这些子问题来寻找原问题的最优解。动态规划与贪婪算法在某些方面有相似之处，比如都考虑问题的解决为一系列决策的结果，但是它们在处理决策的方式上存在本质的区别。在贪婪算法中，一旦做出了决策，就是不可逆的，而在动态规划中，会回溯检查决策序列中是否包含最优子序列，以确保整体的最优性。
动态规划广泛应用于各种问题中，其中一个重要的问题是所有顶点对最短路径问题（All-Pairs Shortest Paths）。这个问题的目标是找出一个有向加权图中任意两个顶点之间的最短路径。对于一个具有n个顶点的图，我们需要找到n(n-1)个最短路径。通常，这些路径不能包含负长度的循环，因为加入负循环不会产生更短的路径。为了找到所有这些路径，动态规划方法涉及重复应用最短路径算法，例如Dijkstra算法或Floyd算法。
Dijkstra算法是最著名的单源最短路径算法，用于找到一个顶点到其他所有顶点的最短路径。Dijkstra算法的基本思想是通过逐渐增长的路径集合来找到最短路径。它需要一个优先队列来维护当前找到的最短路径，并且每次从队列中取出距离源点最近的顶点来更新其他顶点的最短路径估计。Dijkstra算法的时间复杂度取决于使用的数据结构，如果使用二叉堆实现优先队列，则时间复杂度为O((V+E)logV)；如果使用斐波那契堆，则为O(VlogV+E)。
Floyd算法，也称为Floyd-Warshall算法，是一种用于寻找所有顶点对之间最短路径的动态规划算法。它适用于包括负权重边的图，但假设图中没有负权重循环。Floyd算法通过不断更新顶点之间的最短路径来工作，每一次迭代都尝试在已有路径中加入一个中间顶点，并检查是否能够得到更短的路径。算法通过构造一个动态规划表c来实现，表中c(i,j,k)表示从顶点i到顶点j通过中间顶点集合{1,2,...,k}时的最短路径长度。算法最终得到一个n阶方阵c(i,j,n)，表示从顶点i到顶点j不经过比n更大的顶点的最短路径长度。Floyd算法的时间复杂度为O(n^3)。
在构建Floyd算法的递归关系时，算法首先初始化一个成本邻接矩阵a，然后对每一个中间顶点k，算法会更新路径长度，如果存在不经过顶点k的路径，则保留原来的路径长度c(i,j,k-1)；如果存在经过顶点k的更短路径，则将路径分成两段，即从i到k和从k到j的路径之和c(i,k,k-1)+c(k,j,k-1)。这样，c(i,j,k)就得到了从i到j经过顶点k的最短路径长度。
动态规划是计算机科学中的一个重要概念，其思想与递归紧密相关，但通过保存已经解决子问题的解来避免重复计算，从而提高了算法的效率。在解决具有重叠子问题和最优子结构特性的问题时，动态规划尤其有效，比如许多图论中的路径问题、背包问题、编辑距离问题等。掌握动态规划的基本原理和实现方法对于解决复杂的优化问题至关重要。
