多段图中的最短路径

多段图中的最短路径问题是经典的动态规划问题之一，其可描述为给定一个有向无环图(DAG 图)，求给定起始顶点到终止顶点的最短路径，此也属于单源最短路径问题。不过 DAG 的独特之处在于其所有的节点都可以线性化成拓扑序列，使得所有边保持由左到右的方向，譬如下图所示：

在文首我们讨论过了，两点之间的最短路径包含最优子结构，即我们可以得出动态规划中的状态转移递推公式。我们关注某个目标顶点 i，到达 i 仅有的途径是经过其直接前驱。如果假设 i 的直接前驱有 k 个顶点：$i_1,i_2,…,i_k$，那我们的状态转移方程可以表述为:

dist(i) = min{dist(i1) + d(i1,i),dist(i2) + d(i2,i),...,dist(ik) + d(ik,i)}

其中 d(i,j)是顶点 i 到 j 的边上的权值，dist(源点) = 0。