写在前面：
多段图是一个有向的无环图。求解从起始点v0到终止点的最短路径的长度， 首先看一下这个问题是否具有最优子结构的性质。对于每一点来说，从v0 到它的最短路径有两种可能，分别是从v0直接到该点或者是从最短的前驱 节点开始到该节点。从这里可以看出有递归的性质，所以使用回溯的方法 也是可以解决的。即从终点开始，依次向前找到最短的路径。由于递归本 身所用的时间较长，并且在回溯的过程中存在重复的工作，所以使用动态规划更好。
动图演示：
多段图： 假设图G=(V,E)是一个带权的有向图，如果可以把顶点集合V划分为k(2<=k<=n)个互不相交的子集Vi(1<=i<=k)，其中V1和Vk分别只有一个顶点s(源点)和一个顶点t(终点)。每组子集的顶点都互不相交，即u∈Vi(始点)与v∈Vi+1(终点)互不相交，且边(u,v)有一个正权重值，这种图称为多段图。 多段图的最短路径问题：
🍓一.创建多段图
1.根据邻接矩阵创建多段图。
2.划分子集：因为多段图可以将顶点划分为k个互不相交的子集，所以将它划分为k段，每段都包含顶点，且每段的顶点互不相交。
3.为每个顶点编号，同一子集的顶点顺序无关紧要。源点s为0，终点t为n-1。
🍇二.证明满足最优性原理
设s，s，s1，s2，……，sp，t是s到t的一条最短路径，且s到s1的路径已经求出，则问题转为s1到t的最短路径，因此s1，s2，……，sp，t构成一条最短路径，如果不是，则设s1，r1，r2，……，rp，t是一条从s1到t的最短路径，则s，s1，r1，r2，……，rp，t是一条从s到t的最短路径且比s，s1，s2，……，sp，t短，因此矛盾，则满足最优性原理。
🍒三.设置子问题
自顶向下 对多段图的边（u,v），用c表示边上的权值，将从源点s到终点t的最短路径记为d（s,t），则从源点0到终点9的最短路径d（0，9）由下式确定：
d（0,9）=min{c01+d（1,9），c02+d（2,9），c03+d（3,9）}
这是最后一个阶段的决策，它依赖于d（1,9）、d（2,9）和d（3,9）的计算结果。
d（1,9）=min{c14+d（4,9），c15+d（5,9）}
d（2,9）=min{c24+d（4,9），c25+d（5,9），c26+d（6,9）}
d（3,9）=min{c35+d（5,9），c36+d（6,9）}
这一阶段的决策又依赖于d（4,9）、d（5,9）和d（6,9）的计算结果。
d（4,9）=min{c47+d（7,9），c48+d（8,9）}
d（5,9）=min{c57+d（7,9），c58+d（8,9）}
d（6,9）=min{c67+d（7,9），c68+d（8,9）}
这一阶段的决策依赖于d（7,9）和d（8,9）的计算。
d（7,9）和d（8,9）可以直接获得（括号中给出了决策产生的状态转移）：
d（7,9）=c79=7（7→9）
d（8,9）=C89=3（8→9）
自底向上 反向求解出最短的路径，得到：最短路径为0→3→5→8→9，长度为16。
🍑建立多段图的邻接矩阵：
动图演示：多段图： 假设图G=(V,E)是一个带权的有向图，如果可以把顶点集合V划分为k(2<=k<=n)个互不相交的子集Vi(1<=i<=k)，其中V1和Vk分别只有一个顶点s(源点)和一个顶点t(终点)。每组子集的顶点都互不相交，即u∈Vi(始点)与v∈Vi+1(终点)互不相交，且边(u,v)有一个正权重值，这种图称为多段图。 多段图的最短路径问题：
目录
🍓一.创建多段图
🍇二.证明满足最优性原理
🍒三.设置子问题
🍓一.创建多段图
1.根据邻接矩阵创建多段图。
2.划分子集：因为多段图可以将顶点划分为k个互不相交的子集，所以将它划分为k段，每段都包含顶点，且每段的顶点互不相交。
3.为每个顶点编号，同一子集的顶点顺序无关紧要。源点s为0，终点t为n-1。
🍇二.证明满足最优性原理
设s，s，s1，s2，……，sp，t是s到t的一条最短路径，且s到s1的路径已经求出，则问题转为s1到t的最短路径，因此s1，s2，……，sp，t构成一条最短路径，如果不是，则设s1，r1，r2，……，rp，t是一条从s1到t的最短路径，则s，s1，r1，r2，……，rp，t是一条从s到t的最短路径且比s，s1，s2，……，sp，t短，因此矛盾，则满足最优性原理。
🍒三.设置子问题
自顶向下 对多段图的边（u,v），用c表示边上的权值，将从源点s到终点t的最短路径记为d（s,t），则从源点0到终点9的最短路径d（0，9）由下式确定：
d（0,9）=min{c01+d（1,9），c02+d（2,9），c03+d（3,9）}
这是最后一个阶段的决策，它依赖于d（1,9）、d（2,9）和d（3,9）的计算结果。
d（1,9）=min{c14+d（4,9），c15+d（5,9）}
d（2,9）=min{c24+d（4,9），c25+d（5,9），c26+d（6,9）}
d（3,9）=min{c35+d（5,9），c36+d（6,9）}
这一阶段的决策又依赖于d（4,9）、d（5,9）和d（6,9）的计算结果。
d（4,9）=min{c47+d（7,9），c48+d（8,9）}
d（5,9）=min{c57+d（7,9），c58+d（8,9）}
d（6,9）=min{c67+d（7,9），c68+d（8,9）}
这一阶段的决策依赖于d（7,9）和d（8,9）的计算。
d（7,9）和d（8,9）可以直接获得（括号中给出了决策产生的状态转移）：
d（7,9）=c79=7（7→9）
d（8,9）=C89=3（8→9）
自底向上 反向求解出最短的路径，得到：最短路径为0→3→5→8→9，长度为16。
🍑建立多段图的邻接矩阵：
int CreatGraph() { int i, j, k; int weight; int vnum, arcnum; printf("请输入顶点的个数:"); scanf_s("%d", &vnum); printf("请输入边的个数:"); scanf_s("%d",&arcnum); for (i= 0; i < vnum; i++) for (j = 0; j < vnum; j++) arc[i][j] = MAX; for (k = 0; k < arcnum; k++) { printf("请输入边的两个顶点和权值:"); scanf_s("%d,%d,%d", &i, &j, &weight); arc[i][j] = weight; } return vnum; }
代码：
int BackPath(int n) { int i, j; int cost[N], path[N]; for (i = 1; i < n; i++) { cost[i] = MAX; path[i] = -1; } cost[0] = 0; path[0] = -1; for (j = 1; j < n; j++) { for (i = j - 1; i >= 0; i--) { if (arc[i][j] + cost[i] < cost[j]) { cost[j] = arc[i][j] + cost[i]; path[j] = i; } } } printf("%d", n - 1); i = n - 1; while (path[i] >= 0) { printf("<-%d", path[i]); i = path[i]; } return cost[n - 1]; }
