10.5.4　求最短路径问题

求A城市和B城市之间的最短路径，可以通过动态规划算法实现。图10.7所示的为A城市可以到达B城市的所有路径。

图10.7　A城市到B城市的路径

为了方便计算，可以用二维表先建立每个经过的节点之间的距离关系，如图10.8所示。左边第一列代表当前阶段节点与顶端第一行所有节点之间的后连接关系（当前阶段节点与后一阶段节点关系），没有关系的设置为0，有关系的设置为节点之间的距离值。

图10.8　用二维表记录前后阶段节点之间的距离关系

从图10.8可以看出，1节点与2节点的距离是5，与3节点的距离是4，于是可以得到1节点到2、3节点的最短距离为4；

2节点到4节点距离为2，到5节点距离为3，于是2节点到4、5节点的最短距离为2，1、2、4节点距离和为5+2=7。(https://www.daowen.com)

把问题分解为求每个节点距离A节点的最优解，从最左边节点开始求解，从前一阶段的节点推算当前节点的最优解。如从4、5节点的最优解推算8节点的最优解；从8、9节点的最优解推算10（B）节点的最优解，得到该题的整体最优解。

为了避免前节点最优解的重复计算，可以把计算结果放回图10.8里，用过程最优解替代当前节点的距离值。

代码文件：10_5_4_MinPath.py

代码执行结果如下：

当前节点的前置节点有多个时，会显示多个重复当前节点的解，如节点9有3个前置节点（可以与图10.7对照）。