本文主要是介绍动态规划法(五)——多段图问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
给定一个多段图，求出多段图中的最短路径和最短路径长度。
什么是多段图？
- 多段图是一个有向、无环、带权 图。
- 有且仅有一个起始结点（原点source） 和 一个终止结点（汇点target）。
- 它有n个阶段，每个阶段由特定的几个结点构成。
- 每个结点的所有结点都只能指向下一个相邻的阶段，阶段之间不能越界。
数据结构
- cost数组：
该数组用于记录以某个结点为起点，到终点t的最短路径长度值。
数组的下标表示结点的编号（因此所有结点都必须从0开始依次编号），数组的值表示：以该结点为起点，到终点的最短路径长度。 - d数组：
该数组用于记录最短路径中出现的所有结点。
下标表示结点的编号，d[i]表示：结点i的后继结点编号。
算法思路
算法流程
- 从前往后依次给所有结点编号；序号必须从0开始，依次递增ÿ
这篇关于动态规划法(五)——多段图问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
