说明：自己在学习动态规划的过程中，碰到求解最短路径问题的实例，而理解了动态规划之后，再理解实例中的逐段累加法可能会让人难以理解。这篇文章主要是对比枚举法、逐段累加法、动态规划法求解最短路径问题的思路以及加法次数

问题：两点之间连线上的数字表示距离，求由A到G的最短路径（问题很常见，不过多描述了）

（图片来源：《运筹学·第三版》清华大学出版社）

为了说明的方便，这里删去图上的EFG节点，只保留A到D节点

这里，从A到D一共有2*3*2 = 12条路径，下面是加法运算次数对比：

法一. 普通计算，枚举法
思路：每条路径是单独计算的，例如：A到B1到C1到D1这条路径，先计算AB1 + B1C1，之后，AB1 + B1C1的和与C1D1相加。

一共12条路径，每条路径上有2次
12*2 = 24次
分别是
AB1 + B1C1 与 AB1C1长度 + C1D1
AB1 + B1C1 与 AB1C1长度 + C1D2
AB1 + B1C2 与 AB1C2长度 + C2D1
AB1 + B1C2 与 AB1C2长度 + C2D2
AB1 + B1C3 与 AB1C3长度 + C3D2
AB1 + B1C3 与 AB1C3长度 + C3D3
AB2 + B2C2 与 AB2C2长度 + C2D1
AB2 + B2C2 与 AB2C2长度 + C2D2
AB2 + B2C3 与 AB2C3长度 + C3D2
AB2 + B2C3 与 AB2C3长度 + C3D3
AB2 + B2C4 与 AB2C4长度 + C4D2
AB2 + B2C4 与 AB2C4长度 + C4D3

法二. 逐段累加法（当理解了动态规划之后，可能会觉得逐段累加不好理解）
思路：先计算所有的A到C的路径长度，并保存，再计算所有的A到D的路径长度，而A到D的路径中包含了一部分已经计算且保存了的A到C的路径，那么这部分就直接调用保存的结果而无需再次计算（以此类推，如果是ABCDE，先计算所有的A到C的路径长度，再计算所有的A到D的路径长度，再计算所有的A到E的路径长度，这就是逐段累加的含义）

先计算A到C，6条路径，每条路径1次加法，一共6次加法
AB1 + B1C1
AB1 + B1C2
AB1 + B1C3
AB2 + B2C1
AB2 + B2C2
AB2 + B2C3
并且这六个结果都保存

再计算A到D，12条路径，每条路径都分为A到C与C到D两部分来看，A到C的路径长度已经计算过且保存了结果，所以对于每条路径来说，只需计算这条路所经过的A到C的路径长度 + 这条路径所经过的CD长度。每条路径都只有1次加法，一共12次加法
分别是
AB1C1长度 + C1D1
AB1C1长度 + C1D2
AB1C2长度 + C2D1
AB1C2长度 + C2D2
AB1C3长度 + C3D2
AB1C3长度 + C3D3
AB2C2长度 + C2D1
AB2C2长度 + C2D2
AB2C3长度 + C3D2
AB2C3长度 + C3D3
AB2C4长度 + C4D2
AB2C4长度 + C4D3

6 + 12 = 18次

可以看出，逐段累加方法相对于枚举法的优势在于，保存所有的逐段累加的计算结果，供之后的计算直接调用

法三. 动态规划法
思路：逆向寻找最短路径，为了和上面两种方法对比，这里以D为起点，A为终点。先计算所有的C到A的路径长度，并保存，而且选出所有的C到A的最短路径长度，再计算所有的D到A的路径长度，而D到A的路径中包含了一部分已经计算、保存且选出的C到A的最短路径，那么这部分就直接调用保存的结果而无需再次计算（以此类推，如果是ABCDE，先计算所有的C到A的路径长度，选出所有的C到A的最短路径长度，再计算所有的D到A的路径长度，选出所有的D到A的最短路径长度，再计算所有的E到A的路径长度）

先计算C到A，6条路径，每条路径1次加法，一共6次加法
AB1 + B1C1
AB1 + B1C2
AB1 + B1C3
AB2 + B2C1
AB2 + B2C2
AB2 + B2C3
并且这六个结果都保存，且选出
C1到A的最短路径长度，AB1C1
C2到A的最短路径长度，AB1C2
C3到A的最短路径长度，AB2C3
C4到A的最短路径长度，AB2C4

再计算D到A，每条D到A的路径都分为D到C与C到A两部分来看，C到A的路径长度已经计算过且保存了结果，且选出了最短路径，所以不必考虑每条C到A的路径，只用考虑C到A的最短路径，而D到C有8条路径，可以认为当从D到达C时直接选用C到A的最短路径到达A。所以，实际上D到A只需要考虑8条路径，对于这8条路径中的每条路径来说，需要计算的是这条路所经过的DC长度 + C到A的最短路径长度。每条路径都只有1次加法，一共8次加法
分别是
AB1C1长度 + C1D1
AB1C1长度 + C1D2
AB1C2长度 + C2D1
AB2C2长度 + C2D2
AB2C3长度 + C3D2
AB2C3长度 + C3D3
AB2C4长度 + C4D2
AB2C4长度 + C4D3

6 + 8 = 14次

可以看出，动态规划相对于逐段累加方法的优势在于，计算D到A的最短路径时，直接取用C到A的最短路径，而不是考虑C到A的全部路径
 

三种方法结合起来对比

动态规划求解多段图最短路径

题目：

分析见源代码注释
源代码：

#include<stdio.h>
#define N 10//定义定点数,编号从1开始
#define M 5//定义层数
#define INF 0x3f3f3f
int graph[100][100];//图的链接矩阵
int num[5] = { 1,4,7,9,10 };//每一层对应的节点最大编号，用于区分每一层
int cost[N+1];//每一个节点从起点到该节点的最短距离
int pos[N + 1];//每一个节点对应最短距离的上一节点,用于后续输出最短路径
void map()
{
	int i,x;
	for (i = 0; i < M-1; i++)//对应每一层，从第二层开始
	{
		x = num[i] + 1;
		while (x <= num[i + 1])//每一层的每个节点
		{
			for (int j = 1; j <= 10; j++)//遍历与该节点有链接关系的上一层节点
			{
				if (graph[j][x] != 0)
				{
					int y = graph[j][x] + cost[j];//该层节点与上一层节点间距离+起点到上一层的最短距离
					if (y < cost[x])//比较大小，求出起点到该节点的最短距离
					{
						cost[x] = y;
						pos[x] = j;
					}
				}
			}
			//printf("%d ", cost[x]);//输出每一个节点对应的最短路径代价
			x++;
		}
	}
}
void showpath()//输出最短路径
{
	int i = N,j=0;
	int a[M-1];
	while (i > 1)
	{
		a[j++] = pos[i];
		i = pos[i];
	}
	printf("最短路径为：");
	for (i = M - 2; i >= 0; i--)
		printf("%d->", a[i]);
	printf("%d\n",N);
}
int main()
{
	for (int i = 1; i <= N; i++)
	{
		cost[i] = INF;
		pos[i] = 1;
	}
	cost[1] = 0;
	pos[1] = 0;
	for (int i = 1; i <= N; i++)
		for (int j = 0; j <= N; j++)
			graph[i][j] = 0;
	graph[1][2] = 4; graph[1][3] = 2; graph[1][4] = 3;//初始化
	graph[2][5] = 10; graph[2][6] = 9;
	graph[3][5] = 6; graph[3][6] =7; graph[3][7] =10;
	graph[4][6] = 3; graph[4][7] =8;
	graph[5][8] = 4; graph[5][9] = 8;
	graph[6][8] = 9; graph[6][9] =6;
	graph[7][8] = 5; graph[7][9] = 4;
	graph[8][10] = 8; 
	graph[9][10] = 4;
	map();
	showpath();
	printf("代价为：%d", cost[N]);
	return 0;
}