最短路与动态规划（一）

运筹学有时候面临的一种场景是求最短路（shortest path）问题：比如城市交通的网络设计，芯片的表面设计等。解决这类问题常用离散动态规划（discrete dynamic）方法。今天我们就来学习这种场景以及解决的算法。

1

抽象为模型

我们用三个与现实场景十分相似的例子来介绍模型以及相关术语。

• 利特尔维尔交通规划

假设你是利特尔维尔城市的交通工程师，下图是该城市的市区街道规划图，图中标注了道路是单行道还是双向道，也标注了汽车通过每条街区所需要的平均时间（单位：秒）.

从调查报告和其他数据中我们可以估计出出行居民的数量、出行的起点和终点，但是他们具体选择怎样的路径则不得而知。交通工程师的一项任务就是估计出居民所选择的路径，从而使得城市管理者能够估计出是否有某条道路会产生拥堵。

为了得到一个不错的初步估计，我们可以首先假设所有的出行居民都会做出理性的决策——也就是选择连接起点和终点的最短路径。因此，我们首先需要找到图中任意两点间的所有最短路径。

要用数学来解决这个问题，首先，先将给定的街区系统抽象为图（graph）或网络（network），图模型我们在机器学习的概率图一块给出了初步定义，在运筹学这里有稍微的不同，为了表达得清晰准确，我们定义：

节点表示网络中的实体、交点和转移点，为了方便，利特尔维尔例子的节点用1到10进行标号。节点之间可能被弧或者边相连（弧特指有方向的边），比如这里用弧表示单向街道，边表示双向街道。

利特尔维尔例子转化为图，表示如下：

有了图，我们可以给路（path）下定义：

路是图中连接