第八章第三节 动态规划
文章目录
动态规划是将要解决的问题分成若干小问题，且这些小问题会被重复调用。如斐波那契数列的计算、Dijkstra算法等。下面介绍解决多源最短路径的Freud算法。
Freud算法
在第k轮，图中每对顶点以$v_{1}, …, v_{k}$为中介的最短路径要么是以$v_{1},…,v_{k-1}$为中介的最短路径，要么是由$v_{i}$到$v_{k}$的最短路径与$v_{k}$到$v_{j}$的最短路径的拼接。
初始时，相邻顶点间的最短路径为这两个顶点，其长度为边的权；不相邻顶点间的最短路径长度记为$\infty$；
算法经$|V|$轮得到图中所有顶点间的最短路径。