最短路问题

最短路问题 何谓最短路？ 最短路问题考虑的是有向网络 N=（V，A，W），其中弧（i,j）∈A 对应的权 又称为弧长或费用。对于其中的两个顶点 s，t∈V,以 s 为起点，t 为终点的 有向路称为 s-t 有向路，其所经过的所有弧上的权（或弧长、费用）之和称为 该有向路的权（或弧长、费用）。所有 s-t 有向路中权最小的一条称为 s-t 最短 路。 ijw 如何得到最短路？ 最短路问题的线性规划描述如下： ( , ) m in i j i j i j A w x ∈ ∑ (1) :( , ) :( , ) 1, , . . 1, , 0 , , ij ji j i j A j j i A i s s t x x s i s t∈ ∈ =⎧⎪ t− = − =⎨⎪ ≠⎩ ∑ ∑ (2) 0ijx ≥ (3) 其中决策变量 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示弧（i,j）是否位于 s-t 路上：当 =1 时，表示弧（i,j） 位于 s-t 路上，当 =0 时，表示弧（i,j）不在 s-t 路上。本来， 应当是 0-1 变量，但由于约束（2）的约束矩阵就是网络的关联矩阵，它是全幺模矩阵，因 此 0-1 变量可以松弛为区间[0，1]中的实数（当用单纯形法求解时，将得到 0-1 整数解）。 ijx ijx ijx ijx 值得注意的是，我们这里将变量 直接松弛为所有非负实数。实际上，如 果 可以取 0-1 以外的整数，则约束条件并不能保证对应于非零 的弧所构成 的结构（记为 P）一定是一条路，因为这一结构可能含有圈。进一步 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，我 们总是假设网络本身不含有负圈，而任何正圈不可能使目标函数最小，因此上 面的约束条件（2），（3）可以保证当达到最优解时，P 如果包含圈，该圈一定 是零圈，我们从 P 中去掉所有的零圈，就可以得到最短路。 ijx ijx ijx 无圈网络与正费用网络一般采用标号设定算法。 Bellman 方程（最短路方程） 将约束条件（2）两边同时乘以-1，得到其对偶问题为： max( )t su u− （4） . . , ( , )j i i js t u u w i j A− ≤ ∀ ∈ （5） 根据互补松弛条件，当 x 和 u 分别为原问题和对偶问题的最优解时： ( ) 0 , ( ,i j j i i j )x u u w i j− − = ∀ ∈ A （6） 因此,当某弧（i，j）位于最短路上时，即对应的变量 ＞0 时，一定有ijx j i iu u w− = j 。但在对偶问题中，如果 u 为最优解，易知 u+c（c 为任意实数） 仍为最优解。因此，u 的具体数值不能唯一确定。不妨令 0su = ，则 u 的具体 数值就可以唯一确定了。 进一步分析可以看出， ju相当于对节点 j 赋予的一个实数值（通常称为“标 号”），在 时0su = ju表示的正好是节点 s 到节点 j 的最短路的长度。因此，可 以得到求解最短路问题的如下递推关系： 0 ( min{ } (8) s j i iji j u u u w≠ =⎧⎪⎨ = +⎪⎩ LLLLLLL LL 7) 当两节点间没有弧相连接时，上面递推式中认为对应的权为无穷大。这就是最 短路问题的动态规划基本方程，称为 Bellman 方程，也称为最短路方程。 正费用网络采用 Dijkstra 算法： 算法的基本思想是：对于 V 中每一个顶点 j，赋予两个数值（通常称为“标号”）： 一个是距离标号 ju，记录的是从起点到该顶点的最短路长度的上界；另一个是 前趋标号 Pred(j)，记录的是当起点 s 到该顶点 j 的一条路长取到该上界 ju时， 该条路中顶点 j 前面的那个直接前趋（节点）。算法通过不断修改这些标号，进 行迭代计算。当算法结束时，距离标号表示的是从期待内到该顶点的最短路长 度。在酸法不断修改这些标号迭代进行计算的过程中，所有顶点实际上被分成 了两类：一类是离起点 s 较近的顶点，它们的距离标号表示的是从点 s 到该顶 点的最短路长度，因此其标号不会在以后的迭代中再被改变（称为永久标号）； 一类是离起点 s 较远的顶点，它们的距离标号表示的只是从点 s 到该顶点的最 短路长度的上界，因此其标号还可能会在以后的迭代中再改变（称为临时标号）。 算法的具体步骤如下： Dijkstra 算法（计算正费用网络 G=（V，A，W）的最短路，起点 s 编号假 定为顶点 1）。 STEP0 （初始化）令 S=Φ， s− =V， 1 0su u= = ，Pred(s)=0;对 V 中的顶 点 j（ j s≠ ）令初始距离标号 ju =∞。 STEP1 如果 S=V，则 ju为节点 s 到节点 j 的最短路路长（最短路距可以 通过数组 Pred 所记录的信息反向追踪获得），结束；否则继续 STEP2。 STEP2 从 s − 中找到距离标号最小的节点 i,把它从 s − 删除，加入 s。对 于所有从 I 出发的弧(i,j)∈A，若 su＞ iu wij+ ，则令 su = ， Pred(j)=I。转 STEP1。 i iu w+ j 其 C++程序为： 求解最短路问题的标号算法一般可以分成两类，即所谓的标号设定算法 （Label-setting algorithm）和标号修正算法(Label-correcting algorithm)。 其共同的特点：在通过迭代过程对标号进行逐步修正的过程中，每次迭代将一 个顶点从临时标号集合中移入永久标号集合中。这样的标号算法称为标号设定 算法，因为每次迭代可以设定一个顶点标号为永久标号。标号算法一般只能用 来求解无圈网络和正费用网络的最短路问题。 对于一般正费用网络的最短路问题，一般采用标号修正算法。它的基本思 想是：在每次迭代过程中，所有顶点的距离标号都是临时标号。实际上，每个 顶点的距离标号表示的是在一定限制条件下，从起点到该节点的最短路的路长。 当迭代终止时，限制条件被完全取消，因此所有顶点标号同时转化为永久标号。 这一方法实质上是采用逐步逼近的思想求解最短路方程，因此有时也称为逐次 逼近法（successive approximation）. Bellman-Ford 算法： 该算法计算从起点到所有其他顶点的最短路。它是 Ford 于 1956 年最早提出的 一种标号修正算法。可以用迭代方程表示如下： (1) 1 (1) 1 ( 1) 0, (9) , 1, (10) min{ ,min( )}, (11) 1 2,1 . j j k k k j j i ij u u w i u u u w k n j n + ⎧ =⎪ = ≠⎪⎨ = +⎪⎪ ≤ ≤ − ≤ ≤⎩ LLLLLLLLLLL LLLLLLLL LL 通过迭代求解上面的方程， 是第 k 次迭代得到的顶点( )kju (1 )j j n≤ ≤ 的临时标 号，最后得到的 即为从起点 s=1 到顶点( 1)nj ju u −= (1 )j j n≤ ≤ 的最短路路长（永 久标号）。在算法执行过程中，与 Dijkstra 算法中用 Pred 数组记录信息类似， 还应该记录相应的中间信息，以便确定最短路。 一般的标号修正算法： STEP0 令距离标号 ，前趋标号 Pred(s)=0；对所有其他节点 j 令0su = ju 无穷大。 STEP1 如果对所有的弧（i,j）有 ju ≤ iu wij+ ，则结束， ju就是从起点 s 到节 点 j 的最短路长，最短路可以通过前趋标号（Pred）获得。否则进 行下一步。 STEP2 找到一条满足 ju＞ iu wij+ 的弧（i,j），令 ju = iu wij+ ，Pred(j)=i，转 STEP1。 改进的标号修正算法： STEP0 令 LIST={s}，距离标号 0su = ，前趋标号 Pred(s)=0；对所有其他节 点 j 令 ju无穷大。 STEP1 如果 LIST=Φ，则结束， ju就是从起点 s 到节点 j 的最短路长，最短 路可以通过前趋标号（Pred）回溯获得。否则进行下一步。 STEP2 从 LIST 中删除一个节点 i,对从 i 出发的每条弧（i,j）判断是否满足 ju＞ iu wij+ 。如果是，则令 ju = iu wij+ ，Pred(j)=i，并令LIST=LISTU{j}. 当从 i 出发的所有弧都检查完以后，转 STEP1。 Floyd-Warshall 算法： (1) (1) ( 1) ( ) 0, (12) , , (13 min{ , }, , , 1, , . (14) ii ij ij k k k k ij ij ik kj u u w i j u u u u i j k n+ ⎧ =⎪⎪ = ≠⎨⎪ = + =⎪⎩ LLLLLLLLLLLLLLLL LLLLLLLLLLLLL L LL ) 这种算法可以看成是标号修正算法的一种推广。通过迭代求解上面的方程， ( )kiju 是第 k 次迭代得到的顶点 i,j 的临时标号，最后得到的 即为从节点 ( ) ( 1)k nij iju u += I 到节点 j 的最短路路长（永久标号）。 算法可以具体描述如下： DTEP0 k=0。对于所有节点 i 和 j，令 (1)ijp =j, =0(可以认为 =0)， = (1) iiu iiw (1) iju ijw （i≠j）(若节点 i 和 j 之间没有弧，认为 ijw=∞)。 STEP1 k=k+1。对于所有节点 i 和 j，若 + ，令 = ， = ；否则令 ( ) ( )k k ij iku u≤ ( )kkju ( 1)kijp + ( )kijp ( 1)k iju + ( )k iju ( 1)k ijp + = ，( )kikp ( 1)kiju + = + 。 ( )k iku ( )k kju STEP2 如果 k=n，结束；否则转 STEP1。