多段图G=(V,E)是一个有向图。它具有如下特征：图中的节点被划分成k>=2个不相交的集合Vi，1<=i<=k,其中V1 与Vk 分别只有一个结点s（源点）和t（汇点）。图中所有的边<u,v> 均具有如下性质：若 ，则 ，1<=i<k-1,且每条边<u,v>均附有成本c<u,v>。从s到t的一条路径成本是这条路径上边的成本和。多段图问题是求s到t的最小成本路径。每个集合 定义图中的一段。由于E得约束，每条从s到t的路径都是从第1段开始，在第k段终止。-Multi-stage graph G = (V, E) is a directed graph. It has the following characteristics: graph node is divided into k>　= 2 disjoint sets Vi, 1 < = i < = k, where V1 and Vk are only one node s (source) and t (Meeting Point ). Figure in all of the edges <u,v> All have the following property: If, then, 1 < = i <k-1,且每条边<u,v> Comes with costs c <u,v> . From s to t, the cost of a path is the path on top of costs and. Multistage Graph Problem is seeking a minimum cost s to t path. Defined by a set figure for each section. Since E was bound, and each path from s to t are from the beginning of paragraph 1, paragraph k in the first end.