直到d(y,)=d-(y,y,y,∈V,则d(y,y)是y,到y,的最短路的权。 例6.3.3书P266图10-21用表格表示。 定义6.3.1设D是赋权有向图，C是D中的一个回路。若C的权w(C)<0,则称C是D的负回路。 不难证明： 1.d(",y)是在最多包含-1个中间点的限制条件下，从y,到v,的最短路。 2.如果D是不含负回路的赋权有向图，则从V,到任一点的最短路必定是初等路，从而最多包含pD)-2 个中间点。这时，一定有dP(y,y)=d-(y,y),y,∈V。 3.如果存在某个v,∈V,使dP(y,y,)≠dP-(v,v),则D一定含负回路，这时显然v,到v,的路的权 无下界。 为加快速度，可用迭代公式： 对=1： d'(y,yj)=wg,j=1…,p t=2,3...:d'(vv)=min(min{d'(v,v)+wi),minfd(vV)+wi,j=1,p 直到d(y,y)=d-(y,y),y,∈V,则d*(y,,)是y,到y,的最短路的权。 或： 对=1： d'(y,y)=wg,j=1,…,p 对=2,4，：d'(y,y)=mind(v,y,ind'(y)+"y,j=l…,p 对=3,5.：d'(v,v)=min{d(y,v),min{d'(y,y)+wn}},j=p,…,1 直到d(y,y)=d-(y,y,y,∈V,则d(y,y)是y,到y,的最短路的权。 6.3.3应用举例 例6.3.4设备更新问题)书P267例13 §6.4网络最大流问题 许多系统包含了流量问题。例如，公路系统中的车辆流，控制系统中的信息流，供水系统中的水流， 金融系统中的现金流，等等。 例如，书P269图10-23，是联结某产品产地y到销点V。的交通网，弧(y,V)上的数字表示y,到v,这 条运输线的最大通过能力。产品交通网从y运到v。现在要求制定一个运输方案，使从y运到y。的产品 数量最多。 6.4.1基本概念和基本定理 1.网络与流 定义6.4.1给定有向图D=(V,A),在V中指定一个点为发点（记作y,),另一个点为收点（记作y,), 其余点为中间点。对于每一条弧(，y)∈A,对应有一个数C,≥0，称为弧(y,y,)的容量。把这种有 向图D称为网络，记作D=(V,A,C)。8 直到 1 ( , ) ( , ), k k sj sj j d vv d vv v V − = ∀∈ ，则 (, ) k s j d vv 是 s v 到 j v 的最短路的权。 例 6.3.3 书 P266 图 10-21 用表格表示。 定义 6.3.1 设 D 是赋权有向图，C 是 D 中的一个回路。若 C 的权 w(C)<0，则称 C 是 D 的负回路。 不难证明： 1． (, ) t s j dvv 是在最多包含 t-1 个中间点的限制条件下，从 s v 到 j v 的最短路。 2． 如果 D 是不含负回路的赋权有向图，则从 s v 到任一点的最短路必定是初等路，从而最多包含 p(D)-2 个中间点。这时，一定有 1 ( , ) ( , ), p p sj sj j d vv d vv v V − = ∀∈ 。 3． 如果存在某个 j v V∈ ，使 1 (, ) (, ) p p s j sj d vv d vv − ≠ ，则 D 一定含负回路，这时显然 s v 到 j v 的路的权 无下界。 为加快速度，可用迭代公式： 对 t=1： 1 ( , ) , 1, , s j sj dvv w j p = = " 对 t=2,3,…： 1 ( , ) min{min{ ( , ) },min{ ( , ) }}, 1, , t tt s j s i ij s i ij ij ij dvv dvv w d vv w j p − < ≥ = + += " 直到 1 ( , ) ( , ), k k sj sj j d vv d vv v V − = ∀∈ ，则 (, ) k s j d vv 是 s v 到 j v 的最短路的权。 或： 对 t=1： 1 ( , ) , 1, , s j sj dvv w j p = = " 对 t=2,4,…： 1 ( , ) min{ ( , ),min{ ( , ) }}, 1, , t tt s j s j s i ij i j dvv d vv dvv w j p − < = += " 对 t=3,5,…： 1 ( , ) min{ ( , ),min{ ( , ) }}, , ,1 t tt s j s j s i ij i j dvv d vv dvv w j p − > = += " 直到 1 ( , ) ( , ), k k sj sj j d vv d vv v V − = ∀∈ ，则 (, ) k s j d vv 是 s v 到 j v 的最短路的权。 6.3.3 应用举例 例 6.3.4(设备更新问题) 书 P267 例 13 §6.4 网络最大流问题 许多系统包含了流量问题。例如，公路系统中的车辆流，控制系统中的信息流，供水系统中的水流， 金融系统中的现金流，等等。 例如，书 P269 图 10-23，是联结某产品产地 1 v 到销点 6 v 的交通网，弧(, ) i j v v 上的数字表示 i v 到 j v 这 条运输线的最大通过能力。产品交通网从 1 v 运到 6 v 。现在要求制定一个运输方案，使从 1 v 运到 6 v 的产品 数量最多。 6.4.1 基本概念和基本定理 1．网络与流 定义 6.4.1 给定有向图 D=(V,A)，在 V 中指定一个点为发点（记作 s v ），另一个点为收点（记作 t v ）， 其余点为中间点。对于每一条弧 (, ) i j vv A ∈ ，对应有一个数 0 ij c ≥ ，称为弧 (, ) i j v v 的容量。把这种有 向图 D 称为网络，记作 D=(V,A,C)