15.053
4 月 2 日，周二
最小费用流问题 网络 G=(N,A) —节点集 N，弧集 A; —弧(i,j)容量 uij —弧(i,j)下限 0 —弧(i,j)费用 cij —节点 i 供/需量 （正号表示供应） 带有费用、容量 供需量的网络图
最短路问题 解最短路问题的 Dijkstra’s 算法
分发：讲稿
目标：输送流的总费用最小 约束：i 节点流入量-i 节点流出量=bi 弧（i,j）上的流量
建模 给出该问题的一般线性规划模型如下：
最短路问题
从源节点(S)到汇节点(T)的最短路是什 么?从节点 1 到节点 6 的最短路是什么? 本节假设： １．从源点到所有其他节点都存在路 ２．所有弧长度都非负
构建线性规划 从源点 s 到汇点 t 的最短路的线性规划问 题一般可表示为：
另一种形式 从源点 s 到汇点 t 的最短路的线性规划问 题可表示为：
其他
有关最短路的一些问题 现实中如何引起的？ —直接应用 —间接（通常很微小）应用 如何解最短路问题？ —Dijkstra’s 算法 如何衡量算法的性能？ —CPU 时间 —性能保障 如何确定解是真的最短路？ —和对偶线性规划联系
可能的运动得分
Flumbaya 是一项非常规水上运动， 运动过程中可以得 2 类分数。进一 个 gymbol 得 7 分，进一个 quasher 得 5 分。电视播报显示最近的比赛 比分是 19：18，这可能么？
Flumbaya 的更多内容 从节点 0 到节点 18 没 有 通路。 因 此 18 分 不可能。
Flumbaya 的更多内容 数据：Gymbol 得 n1 分，Quasher 得 n2 分 确定得分是否可为 q 网络图：G=(N,A)，其中 N={0,…q} 对每个节点 j=0 到 q-n1 ,(j,j+n1)∈A， 对每个节点 j=0 到 q-n2 , (j,j+n2)∈A 问题： G 中有从节点 0 到 q 的路径么？ 图 提示：若 n1 和 n2 除了 1 和-1 之外没有公 共整数约数，则不可能的得分数是 证明需要更多事实。警示： （ (n1-1)(n2-1)/2。 证明是很困难的）
间接应用：寻找最优段落编排 通过最优选择每行间断点， eX 将段落最 T 优分解。它有一个子程序可以计算从第 i 个单词到第 j-1 个单词的引力 F(i,j)。 如何 运用 F(i,j)，建立一个最短路解决段落分 解问题？
间接应用：寻找最优段落设计
通过最优选择每行间断点， TeX 将段落最优分解。它有 一个子程序可以计算从第 i 个单词到第 j-1 个单词的引 力 F(i,j)。如何运用 F(i,j)，建 立一个最短路解决段落分解 问题？ 每个单词对 应于一个节 点 , 弧 (i,j) 表 示行从第 i 个单词到第 j-1 个单词。 从 Tex 到 end 对应一段落 分解。
路径的值 叫做路径 的
“ugliness” 。
关于段落问题例子 n 个不同的肯定否定决策 决策 j: —肯定： 从第 j 个单词开始形成一行 —否定： 不从第 j 个单词开始形成行 每个肯定决策的费用依靠下面的肯 定决策 —f(i,j)是
假定第 j 个单词从下行开始 时，从第 i 个单词开始行的费用。 运用节点 1,2……n+1 建立最短路问 题，其中弧(i,j)的费用是 f(i,j)。从节点 1 到节点 n+1 的最短路是什么？
数据压缩中的应用：近似分段线性函数 输入：分段线性函数 — n 个 点 ,a1=(x1,y1),a2=(x2,y2),… ， an=(xn,yn) —x1
近似分段线性函数 目标：用少量的点近似函数 f —c*: 加入每个点的费用 —c36=|a4-b4|+|a5-b5|=误差总和（其他 都没有错误）
关于近似函数 n 个不同的肯定否定决策 决策 j: —肯定：选择第 j 个单词 —否定：不选择第 j 个单词 每个肯定决策的费用依靠下面的肯 定决策 —cij 是考虑选择第 i 个点，第 i+1 个 点， …第 j-1 个点到第 j 个点的费用。 运用节点 1,...n 建立最短路问题，其 中弧(i,j)的费用是 cij。从节点 1 到节点 n 的最短路是什么？
最短路问题的 Dijkstra 算法 与同伴 一起观 察， 寻找 最短路。 练习：寻找从节点 1 到其他节点的最短 路，用标签 d(i)标记距离，以及每个节点 直接的前节点 pred(i)。 d(1)=0, pred(1)=0 d(2)=2, pred(2)=1 按照递增顺序，确定到节点 1 的其他距 离。
最短路算法的关键步骤 令 d( )代表暂时的标签距离向量 d(j)是从起始节点到节点 j 某路径的 距离。 刷新程序
Procedure Update(i) for each (i,j)∈ A(i) do if d(j) > d(i) + cij then d(j) : = d(i) + cij and pred(j) : = i;
至此，从节点 1 到 j 的最短路长 78。
最短路算法的关键步骤 令 d( )代表暂时的标签距离向量 d(j)是从起始节点到节点 j 的路径的 距离。 刷新程序
Procedure Update(i) For each (i,j)∈A(i) do if d(j) > d(i) + cij then d(j) : = d(i) + cij and pred(j) : = i;
Dijkstra 算法 距离初始化 LIST= 暂 时 节点集。
从 LIST 中选 择标签距离最 小的节点 i， 执 行刷新程序
Update(i)。
p(1,j)是从节点 1 到 j 的路径， 72。 长
一个例子
观察流出 i 点的弧， 刷 新 d(), pred(), 和 LIST.
Dijkstra 算法的计算结果 要从节点 j 寻找最短 路， 从节点 回塑到源 点。
结束
找到 LIST 中距离最 小的节点 i.
Dijkstra 算法提供了从节点 1 到其他节点 的最短路。它提供了一颗最短路树。
运算时间评价 Dijkstra 算法当前形式是有效的，运 算时间以 n 的平方方式增长。 算法可以改造得更加有效 实际运算中，运算时间与弧的数量 呈线性关系（或者几乎是） 。
线绳解与对偶线性规划
令 d(j)代表起始点到节点 j 的距离。 对偶规划： Max d(t)-d(s) s.t. d(s)=0 d(j)
线绳解 线绳解
想象用相同长度的线替代弧， 那么弧(1,3) 将被连接节
点 1 和 3 的长为 4 英尺的线 段代替。 现在一手抓住节点 1，一手抓住节点 6， 拉紧线。
是否得到从节点 1 到 节点 6 的最短路？ 若是，为什么？ 注意：在某种意义上 是最小化节点 1 到 6 物理上的距离。
总结 最短路问题的直接和间接应用。 Dijkstra 算法可以按照到源点距离递 增顺序，计算节点 1 到其他节点的 最短路径。 瓶颈步骤在于确定最短距离的标 签。通过加速本步，可以获得极有 效率的算法。 线绳解是对偶线性规划的最优解， 也是最短路问题的最优解。
一些最终注解 最短路问题多次在网络优化中出现 与动态规划有很有趣的联系 还有其他求解技术，后面将介绍一 种。