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

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

问题描述

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

什么是多段图？

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

数据结构

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

算法思路

算法流程

1. 从前往后依次给所有结点编号；序号必须从0开始，依次递增ÿ