动态规划法(五)——多段图问题

问题描述

给定一个多段图，求出多段图中的最短路径和最短路径长度。

什么是多段图？

• 多段图是一个有向、无环、带权 图。
• 有且仅有一个起始结点（原点source） 和 一个终止结点（汇点target）。
• 它有n个阶段，每个阶段由特定的几个结点构成。
• 每个结点的所有结点都只能指向下一个相邻的阶段，阶段之间不能越界。

数据结构

• cost数组： 该数组用于记录以某个结点为起点，到终点t的最短路径长度值。 数组的下标表示结点的编号（因此所有结点都必须从0开始依次编号），数组的值表示：以该结点为起点，到终点的最短路径长度。
• d数组： 该数组用于记录最短路径中出现的所有结点。 下标表示结点的编号，d[i]表示：结点i的后继结点编号。

算法思路

算法流程

1. 从前往后依次给所有结点编号；序号必须从0开始，依次递增，同一阶段的结点顺序可以随意；
2. 创建数组cost和d，分别记录每个结点的最短路径长度 和 每个结点最短路径的前驱结点；
3. 从最后一个结点开始，从后向前，依次计算每个结点的cost值和d值；
4. 直到将所有结点都计算完毕后，即可得到最短路径。

每个结点cost和d的计算方法

设当前要计算cost[i]的值。

1. 找到i结点所有的出边，假设出边的终点分别是a、b、c，边上的权值分别是w1、w2、w3；
2. 分别计算w1+cost[a]、w2+cost[b]、w3+cost[c]，将其中最小的那个值作为cost[i]；并将最小的那个后继结点作为d[i]。