差分约束系统

（本文假设读者已经有以下知识：最短路径的基本性质、Bellman-Ford算法。

）比如有这样一组不等式：X1 - X2 <= 0X1 - X5 <= -1X2 - X5 <= 1X3 - X1 <= 5X4 - X1 <= 4X4 - X3 <= -1X5 - X3 <= -3X5 - X4 <= -3不等式组(1)全都是两个未知数的差小于等于某个常数（大于等于也可以，因为左右乘以-1就可以化成小于等于）。

这样的不等式组就称作差分约束系统。

这个不等式组要么无解，要么就有无数组解。

因为如果有一组解{X1, X2, ..., Xn}的话，那么对于任何一个常数k，{X1 + k, X2 + k, ..., Xn + k}肯定也是一组解，因为任何两个数同时加一个数之后，它们的差是不变的，那么这个差分约束系统中的所有不等式都不会被破坏。

差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。

即对于任何一条边u -> v，都有：d(v) <= d(u) + w(u, v)其中d(u)和d(v)是从源点分别到点u和点v的最短路径的权值，w(u, v)是边u -> v的权值。

显然以上不等式就是d(v) - d(u) <= w(u, v)。

这个形式正好和差分约束系统中的不等式形式相同。

于是我们就可以把一个差分约束系统转化成一张图，每个未知数Xi对应图中的一个顶点Vi，把所有不等式都化成图中的一条边。

对于不等式Xi - Xj <= c，把它化成三角形不等式：Xi <= Xj + c，就可以化成边Vj -> Vi，权值为c。

最后，我们在这张图上求一次单源最短路径，这些三角形不等式就会全部都满足了，因为它是最短路径问题的基本性质嘛。

话说回来，所谓单源最短路径，当然要有一个源点，然后再求这个源点到其他所有点的最短路径。

那么源点在哪呢？我们不妨自已造一个。

算法导论（第三版）－复习－第六部分图论22-26［转］22习题22.1-5 有向图G(V, E)的平⽅图。

链表表⽰时，对每结点u的Adj[u]中所有v加⼊队列，后边出队边将Adj[v]加⼊Adj[u]中。

矩阵表⽰时，若w[i, j]、w[j, k]同时为1则将w[i, k]置1.习题22.1-6 O(V)的时间寻找通⽤汇点。

汇点的特征是邻接矩阵的第j列除[j, j]外所有元素为1. 可将每⾏调整[j ,j]后作为⼀个整数，所有整数与运算，为1的位是汇点。

习题22.1-7 有向⽆环图的关联矩阵B，BB’每个元素C[i, j]=∑B[i, k]*B’[k, j]=∑B[i, k]*B[j, k]，即同时进i, j两结点与同时出i, j的结点总数-⼀进⼀出i, j两结点的结点总数。

习题22.2-7 类似BFS，d mod2为0则标为B（娃娃脸），d mod2为1则标为H（⾼跟鞋）。

但若有边连接相同类的结点，则⽆法划分。

wrestler(G){for each u in G{(u,v)=Adj[u];if(v.mark==u.mark){throw error;}if(v.d==NIL) {v.d=u.d+1; v.mark=v.d mod 2;}}}习题22.2-8 任意点之间的最短路径。

重复的Dijktra算法或Floyd-Warshall算法习题22.2-9 ⽆向图扩展为有向图。

问题变成要遍历所有边⼀次。

访问结点u时，将u的⼦结点v的其他边都可视为⼦集v，问题等价于u到v，访问v的集合，v到u。

u标为visiting⼊列，然后访问v，v标为visiting⼊列，然后访问v的后继结点，访问过的边标为visited，返回到visiting的点时，如果该点所有连接的边都标为visited只剩⼀条返回上级的边，则返回上级结点并将点标为visited，v出列，访问u的其他⼦结点，最终u出列。

全部结点出列后达到遍历所有边⼀次。

Contents一、定义二、详解三、例题一、定义（百度百科）：如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。

亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。

求解差分约束系统，可以转化成图论的单源最短路径（或最长路径）问题。

观察xj-xi<=bk，会发现它类似最短路中的三角不等式d[v]<=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。

因此，以每个变量xi为结点，对于约束条件xj-xi<=bk，连接一条边(i,j)，边权为bk。

我们再增加一个源点s,s与所有定点相连，边权均为0。

对这个图，以s为源点运行Bellman-ford算法（或SPFA算法），最终{d[ i]}即为一组可行解。

例如，考虑这样一个问题，寻找一个5维向量x=(xi)以满足：这一问题等价于找出未知量xi，i=1,2,…,5，满足下列8个差分约束条件：x1-x2≤0x1-x5≤-1x2-x5≤1x3-x1≤5x4-x1≤4x4-x3≤-1x5-x3≤-3x5-x4≤-3该问题的一个解为x=(-5,-3,0,-1,-4)，另一个解y=(0,2,5,4,1)，这2个解是有联系的：y中的每个元素比x 中相应的元素大5。

引理：设x=(x1,x2,…,xn)是差分约束系统Ax≤b的一个解，d为任意常数。

则x+d=(x1+d,x2+d,…,xn+d)也是该系统Ax≤b的一个解。

bellman-ford算法伪代码：for each v V do d[v] <-- 无限大; d[s] <-- 0Relaxationfor i =1,...,|V|-1 dofor each edge (u,v) 属于E dod[v] <-- min{d[v], d[u]+w(u,v)}Negative cycle checkingfor each v 属于V do if d[v]> d[u] + w(u,v) then no solution在实际的应用中，一般使用SPFA(Shortest Path Fast Algorithm)算法来实现。

差分约束系统在一个差分约束系统(system of difference constraints)中，线性规划矩阵A的每一行包含一个1和一个-1，A的其他所有元素都为0。

因此，由Ax≤b给出的约束条件是m个差分约束集合，其中包含n个未知量，对应的线性规划矩阵A为m行n列。

每个约束条件为如下形式的简单线性不等式：xj-xi≤bk。

其中1≤i,j≤n，1≤k≤m。

例如，考虑这样一个问题，寻找一个5维向量x=(xi)以满足：这一问题等价于找出未知量xi，i=1,2,…,5，满足下列8个差分约束条件：x1-x2≤0x1-x5≤-1x2-x5≤1x3-x1≤5x4-x1≤4x4-x3≤-1x5-x3≤-3x5-x4≤-3该问题的一个解为x=(-5,-3,0,-1,-4)，另一个解y=(0,2,5,4,1)，这2个解是有联系的：y中的每个元素比x中相应的元素大5。

引理：设x=(x1,x2,…,xn)是差分约束系统Ax≤b的一个解，d为任意常数。

则x+d=(x1+d,x2+d,…,xn+d)也是该系统Ax≤b的一个解。

约束图在一个差分约束系统Ax≤b中，m X n的线性规划矩阵A可被看做是n顶点，m条边的图的关联矩阵。

对于i=1,2,…,n，图中的每一个顶点vi对应着n个未知量的一个xi。

图中的每个有向边对应着关于两个未知量的m个不等式中的一个。

给定一个差分约束系统Ax≤b，相应的约束图是一个带权有向图G=(V,E)，其中V={v0,v1,…,vn}，而且E={ (vi,vj) : xj-xi≤bk是一个约束}∪{ (v0,v1) , (v0,v2) , … , (v0,vn) }。

引入附加顶点v0是为了保证其他每个顶点均从v0可达。

因此，顶点集合V由对应于每个未知量xi的顶点vi和附加的顶点v0组成。

边的集合E由对应于每个差分约束条件的边与对应于每个未知量xi的边(v0,vi)构成。

如果xj-xi≤bk是一个差分约束，则边(vi,vj)的权w(vi,vj)=bk（注意i和j不能颠倒），从v0出发的每条边的权值均为0。

差分约束算法差分约束算法（Difference Constraint Algorithm）是一种用于求解差分约束系统的方法，差分约束系统是一种特殊的线性约束系统，其中约束关系为“某个变量的值与另一个变量的差的绝对值不超过某个常数”。

差分约束算法的基本思想是通过对约束条件进行适当的转换，构造一个有向图，并利用拓扑排序的方法求解变量的取值范围。

具体步骤如下：1. 将差分约束系统中的每个差分约束关系转化为两个线性约束关系。

例如，对于约束 a - b ≤ c，可以将其转化为a ≤ b + c 和b ≤ a - c；对于约束 a - b ≥ c，可以转化为a ≥ b +c 和b ≥ a - c。

2. 根据转化后的约束关系构造一个有向图，图中的每个变量表示一个节点，约束关系表示节点间的有向边。

对于每个约束关系a ≤ b + c，构造一条从节点 a 到节点 b 的有向边，边的权重为 c；对于每个约束关系a ≥ b + c，构造一条从节点 b 到节点a 的有向边，边的权重为 c。

3. 对构造的有向图进行拓扑排序，得到拓扑排序的顺序。

4. 根据拓扑排序的顺序，依次计算每个节点的取值范围。

对于每个节点 a，初始化其取值范围为负无穷大到正无穷大。

对于节点 a 的每个后继节点 b，更新节点 b 的取值范围为节点 a 的取值范围加上边的权重。

重复此步骤，直到没有节点的取值范围发生变化，即达到稳定状态。

5. 根据计算得到的每个节点的取值范围，判断差分约束系统是否可解。

如果存在某个节点的取值范围为负无穷大到正无穷大，则差分约束系统无解；否则，取值范围即为差分约束系统的解。

差分约束算法的时间复杂度为 O(nm)，其中 n 是变量的个数，m 是约束关系的个数。

这种算法通常用于求解动态最短路径等问题，具有较高的效率。

Allegro16.3约束设置Allegro16.3约束设置差分对的约束设置第一步，差分对的设置差分对的设置有很多方法，下面介绍两种最常用的方法。

1．点击菜单Logic→Assign Differential Pair... 弹出以下对话框。

点击你想要创建差分对的Net1和Net2,填入差分的名字，点击Add后就成功创建了差分对。

点击Auto Generate按钮后，弹出以下对话框：在第一个输入框填入Net的主要名字后，在下面的框中填入差分线的标志如N，P。

点击Generate即可自动产生差分对。

2.在约束管理器中设置差分对。

在DSN上点击右键，在菜单中选择Create→Differential Pair。

即可弹出下面的对话框。

和上一种方法的设置差不多，这里就不再叙述了。

第二步差分对约束规则的设置差分对各项约束可以在约束管理器中的Electric→Net→routing→Differential Pair中直接在各差分对上填入各项约束数值就可生效，但更好的方法是创建约束规则后赋给各个差分对。

在DSN上点击右键，在菜单中选择Create→Electrical CSet后，弹出下面的对话框;输入规则名后点Ok，在Electric→constraimt set→outing→Differential Pair中可以看到新规则。

在表格中输入各项数值即可完成新规则的设置。

如图所示差分对约束参数主要有以下几个：1coupling paramaters 主要包括了Primary Gap 差分对最优先线间距（边到边间距）。

Primary Width 差分对最优先线宽。

Neck Gap 差分对Neck模式下的线间距（边到边间距），用于差分对走线在布线密集区域时切换到Neck值。

Neck Width差分对Neck模式下的线宽，用于差分对走线在布线密集区域时切换到Neck值。

如图所示设置数值时在表格中右键菜单中选择change，会出现以下各层数值表格，可以在每一层上设置不同的数值。

差分对的约束设置第一步，差分对的设置差分对的设置有很多方法，下面介绍两种最常用的方法。

1．点击菜单Logic→Assign Differential Pair... 弹出以下对话框。

点击你想要创建差分对的Net1和Net2,填入差分的名字，点击Add后就成功创建了差分对。

点击Auto Generate按钮后，弹出以下对话框：在第一个输入框填入Net的主要名字后，在下面的框中填入差分线的标志如N，P。

点击Generate即可自动产生差分对。

2.在约束管理器中设置差分对。

在DSN上点击右键，在菜单中选择Create→Differential Pair。

即可弹出下面的对话框。

和上一种方法的设置差不多，这里就不再叙述了。

第二步差分对约束规则的设置差分对各项约束可以在约束管理器中的Electric→Net→routing→Different ial Pair中直接在各差分对上填入各项约束数值就可生效，但更好的方法是创建约束规则后赋给各个差分对。

在DSN上点击右键，在菜单中选择Create→Electrical CSet后，弹出下面的对话框;输入规则名后点Ok，在Electric→constraimt set→outing→Differential Pair中可以看到新规则。

在表格中输入各项数值即可完成新规则的设置。

如图所示差分对约束参数主要有以下几个：1coupling paramaters 主要包括了Primary Gap 差分对最优先线间距（边到边间距）。

Primary Width 差分对最优先线宽。

Neck Gap 差分对Neck模式下的线间距（边到边间距），用于差分对走线在布线密集区域时切换到Neck值。

Neck Width差分对Neck模式下的线宽，用于差分对走线在布线密集区域时切换到Neck值。

如图所示设置数值时在表格中右键菜单中选择change，会出现以下各层数值表格，可以在每一层上设置不同的数值。

Vivado差分时钟管脚约束1. 引言在FPGA设计中，时钟是一个关键因素。

时钟的稳定性和准确性对于设计的正确性和性能至关重要。

在Vivado工具中，差分时钟是一种常见的时钟类型，它可以提供更好的抗干扰能力和噪声容限。

本文将介绍如何在Vivado中进行差分时钟管脚约束的配置，以确保设计的正确性和稳定性。

2. 差分时钟概述差分信号由一对相互补偿的信号组成，其中一个信号是另一个信号的反相。

这种信号传输方式可以提供更好的抗干扰能力和噪声容限，因此在高速数据传输和时序要求严格的应用中广泛使用。

在FPGA设计中，差分时钟常用于数据接口、存储器接口、高速通信等场景。

为了正确地使用差分时钟，在设计过程中需要对其进行适当的约束设置。

3. Vivado工具约束设置流程步骤1：创建约束文件首先，在Vivado工程目录下创建一个新的约束文件（以.xdc为后缀），例如constraints.xdc。

步骤2：定义差分时钟在约束文件中，使用create_clock命令定义差分时钟。

语法如下：create_clock -period <period> -waveform {<rise_time><fall_time>} [get_pins <c lock_pins>]其中： - <period>表示时钟周期，单位为纳秒（ns）； - <rise_time>和<fall_time>表示上升沿和下降沿的时间，单位为纳秒（ns）； - <clock_pins>表示与差分时钟相关的管脚。

例如，定义一个50MHz的差分时钟：create_clock -period 20 [get_pins {clk_p clk_n}]步骤3：设置约束属性除了定义差分时钟周期外，还可以设置其他约束属性来进一步优化设计。

以下是一些常见的约束属性及其用法：•set_input_delay：设置输入延迟；•set_output_delay：设置输出延迟；•set_false_path：设置虚假路径（不进行时序优化）；•set_max_delay：设置最大延迟。

ALLEGRO约束规则设置步骤[图解]ALLEGRO 约束规则设置步骤[图解]本文是我对约束规则设置方面的一些理解，希望对新手能有所帮助。

由于本人水平有限，错误之处难免，希望大家不吝赐教！在进行高速布线时，一般都需要进行线长匹配，这时我们就需要设置好constraint 规则，并将这些规则分配到各类 net group 上。

下面以 ddr为例，具体说明这些约束设置的具体步骤。

1．布线要求DDR 时钟:线宽 10mil，内部间距 5mil，外部间距30mil，要求差分布线，必需精确匹配差分对走线误差，允许在＋20mil 以内DDR 地址、片选及其他控制线：线宽 5mil，内部间距 15mil，外部间距20mil，应走成菊花链状拓扑，可比ddrclk 线长1000－2500mil，绝对不能短DDR 数据线，ddrdqs，ddrdm线：线宽 5mil，内部间距 15mil，外部间距20mil，最好在同一层布线。

数据线与时钟线的线长差控制在 50mil 内。

2．根据上述要求，我们在 allegro 中设置不同的约束针对线宽（physical），我们只需要设置3 个约束：DDR_CLK, DDR_ADDR, DDR_DATA设置好了上述约束之后，我们就可以将这些约束添加到net上了。

点击 physical rule set 中的attac h……，再点击右边控制面板中的more，弹出对话框如上图所示，找到 ckn0和 ckp0，点击 apply，则弹出选中左边列表中的NET_PHYSICAL_TYPE, 在右边空格内输入DDR_CLK, 点击apply，弹出即这两个 net已经添加上了 NET_PHYSICAL_TYPE 属性，且值为DDR_CLK.类似的，可以将DDR 数据线，数据选通线和数据屏蔽线的NET_PHYSICAL_TYPE 设为DDR_DATA, DDR 地址线，片选线，和其他控制线的 NET_PHYSICAL_TYPE 设为DDR_ADDR. 上述步骤完成后，我们就要将已经设好的约束分配到这些 net group 上。

数与图的完美结合-------浅析差分约束系统华中师大一附中冯威[摘要]在面对多种多样的问题时，我们经常会碰到这样的情况：往往我们能够根据题目题面意思来建立一些简单的模型，但却面对这些模型无从下手。

这时我们应该意识到，也许能够将这种模型与其他的模型之间搭起一座桥梁，使我们能够用更简单直接的方式解决它。

这里我们介绍一种方法，它很好地将某些特殊的不等式组与图相联结，让复杂的问题简单化，将难处理的问题用我们所熟知的方法去解决，它便是差分约束系统。

这里我们着重介绍差分约束系统的原理和其需要掌握的bellman-ford算法。

然后通过zju1508和zju1420两道题目解析差分约束系统在信息学题目中的应用，并逐渐归纳解决这类问题的思考方向。

[目录]◆关键字 (2)◆Bellman-ford算法 (2)◇算法简单介绍 (2)◇算法具体流程 (2)◇例题一ZJU2008 (4)◆差分约束系统 (5)◇例题二ZJU1508 (5)◇线性程序设计 (7)◇差分约束系统 (7)◇例题三ZJU1420 (8)◆结语 (9)◆附录 (9)[关键字] 差分约束系统、不等式、单元最短路径、转化[正文]在分析差分约束系统之前，我们首先介绍一个解决单元最短路径问题的Bellman Ford算法，它的应用十分广泛，在差分约束系统中更充当着重要的角色。

Bellman-ford 算法算法简单介绍这个算法能在更一般的情况下解决最短路的问题。

何谓一般，一般在该算法下边的权值可以为负，可以运用该算法求有向图的单元最长路径或者最短路径。

我们这里仅以最短路径为例。

Bellman ford 类似于Dijkstra算法，对每一个节点v∈V，逐步减小从起点s到终点v最短路的估计量dist[v]直到其达到真正的最短路径值mindist[v]。

Bellman-ford算法同时返回一个布尔值，如果不存在从源结点可达的负权回路，算法返回布尔值TRUE，反之返回FALSE。

如何实现差分线的约束设计？一、差分线的一般要求一般而言，在PCB设计时对差分线的约束有：基本等长，两根差分线的长度差小于20～50mil；差分线在同一层走线，并尽可能的靠近；差分线和差分线间，差分线和其他网络间，要有20mil以上的间距对于有差分阻抗要求的差分线，严格控制差分线的宽度和间距，严格控制差分线在那一层走线二、在allegro中，实现差分线的约束设计基本步骤如下：1)定义差分线，告诉规则编辑器那些网络是差分线；2)在约束设置器的“spacing rule set”中设置差分线和差分线间，差分线和其他网络的间距；设置两根差分线间最大的长度差，默认得间距和最大的间距；3)在约束设置器的“physical rule set”中设置差分线的线宽；4)打开DRC；5)设置环境变量drc_diff_pair_overide or drc_diff_pair_primary_separation_tolerance三、例子：1)定义差分线。

点击菜单“logic”→“assign differential pair”，出现如下界面：在“Net Selection Area”中的下拉框中选择一对差分线，分别出现在“Rule Information”中“NET 1”和“NET 2”的位置上，在“Rule Name”中给这一对差分线一个名字，如：DIFFPAIR1、DIFFPAIR2等等，点击按钮ADD，这对差分线出现在“Rule Selection Area”中，对所有差分线重复上述步骤。

点击按钮APPL Y，点击OK退出。

2)在规则编辑器的“Spacing Rule Set”中设置差分线和差分线间，差分线和其他网络的间距；设置两根差分线间最大的长度差，默认得间距和最大的间距；点击菜单“Setup”→“Constraints…”→“Spacing Rule Set”→“Set Vaule”，依次出现如下两种界面：设置约束名为DIFF_TEST_1和DIFF_TEST_2，适用的SUBCLASS为ALL ETCH（根据实际情况定），差分线和差分线间，差分线和其他网络的间距line to line设置为20MIL；注意：在Differential Pair一栏中设置两根差分线间最大的长度差，默认的间距和最大的间距，这一栏有四个变量：Length Tolerance：两根差分线间最大的长度差，设置为20～50milPrimary Max Sep：一般情况下两根差分线间允许的最大间距，设为8milSecondary Max Sep：特殊情况下（如打过孔，从PIN出线等）两根差分线间允许比Primary Max Sep大的间距，设置为20Mil，这样在特殊情况下，两根差分线间允许有20＋8MIL的间距，超过这个间距就会出DRC。

这里我们脱离矩阵来讲述差分约束系统。

事实上，当你掌握了本文的算法后，不难将其对应到矩阵问题上去。

差分约束系统是指形如AX<=B 的一个不等式组，（如果A,B表示两个矩阵，则其中A的每行恰有一个1和一个-1，其它元素都是0）。

我们研究差分约束系统，就是要求出满足这个系统的约束条件（也就是简单线性不等式组xj-xi<=bk ）的解。

差分约束系统可以转化为图论的最短路模型，从而巧妙地解决一些很难的问题。

下面我们以一个不等式组来说明这个算法。

（图片比较难做，暂时先拿算法导论上的图片凑合吧。

）假设有不等式组X1 - X2 <= 0X1 - X5 <= -1X2 - X5 <= 1X3 - X1 <= 5X4 - X1 <= 4X4 - X3 <= -1X5 - X3 <= -3X5 - X4 <= -3这个不等式组体现了约束条件的一个特点：全都是两个未知数的差小于等于某个常数（如果是大于等于，可以在左右乘以-1）。

而这个不等式组要么无解，要么就有无数组解。

这是显然的：如果存在一组解{X1, X2, ..., Xn} ，那么对于任何一个常数k，{X1 + k, X2 + k, ..., Xn + k} 也是满足条件的一组解，因为任何两个数同时加一个数之后，它们的差是不变的，它并不会破坏某个不等关系。

联系到图论的三角不等式：对于任何一条边u -> v ，都有：d(v) <= d(u) + w(u, v)其中d(u)和d(v)是从源点分别到点u和点v的最短路径的权值，w(u, v) 是边u -> v 的权值。

将d(u) 移到左边，得到不等d(v) - d(u) <= w(u, v)。

这个形式正好和差分约束系统中的不等式形式相同。

所以我们可以将一个差分约束系统转化成一个单源最短路径问题。

我们把一个差分约束系统转化成一张图，每个未知数Xi 对应图中的一个顶点Vi ，把所有不等式都按下面的思想转化成图中的一条边。

差分约束系统poj1201 ，poj1275的解题报告现在发现刘汝佳写的书真的是给高手看的！。

要是一个半懂的人去看这本书根本不知所云。

简直就是晦涩难懂。

但是一旦把问题搞懂了再去看，就发现居然这个书全讲的是重点。

看来这本书只适合于做指导用。

我基本上没怎么看懂这个书。

这几天做差分系统的题的时候，经常碰到这种情况：为什么题目明明要求的是求某某值的最小值。

但找的资料上却说的用最长路求法。

还有的地方要求某函数值的最大值，但用的方法却是求最短路的方法。

到底是求最短路还是求最长路？最终我发现了。

只要是能用bellman_ford解决的差分约束系统，既可以用最长路求法求得，也可以用最短路求得。

并且部分可以用Dijkstra解决！其实个人觉得用“单原点最短路，单原点最长路求法”这个两个说法来描述用bellman_ford 解决差分约束系统是不准确的。

在一般的最短路径求法中对应的松弛操作为：If dist[b]》dist[a]+ w[a][b] thendist[b]= dist[a]+ w[a][b]。

（1）然而在所谓的最长路求法中松弛操作变为了If dist[b]《dist[a]+ w[a][b] thendist[b]= dist[a]+ w[a][b]。

（2）也就是说，最短路就是对应（1）号松弛方法，最长路对应（2）号而已。

现在先来看看一般的例子：假如有如下不等式组：（即求出来的最终答案要保证下列不等式成立）s[bi] -s[ai]>= ci; 0<=ai，bi<= max; i=1，2，3，。

现在求s[max]的最小值.用求最长路的方法：即用（2）号松弛方法先将不等式变形：s[bi]>=s[ai]+ci;即保证s[bi] 不小于s[ai]+ci;而（2）号松弛操作的作用也是这个。

即保证dist[b]不小于dist[a]+ w[a][b]于是这个个不等式便与这种松弛操作统一了。

所以就设a到b的路径为ci。