标号法的基本原理是累进比较。初始时,l(v)=0,l(v):=∞,(v≠v),S={v0} S=\S。然后算法逐步修改S中顶点的标号。第i步时,对S中每个v,只对刚进入S 的点v计算d(vo,v)+w(vv)(即l(v)+w(vv)),并与(v)进行比较,取其较小的一个 作为的新标号,即l(v):=min{(v),l(v)+w(v)}。因为对在v之前进入S的点 ,v1…,v1,d(Vo,vk)+w(vv)(k=1,2,…}-1)的值及其大小信息已含于(v)之中, 因此只需计算一个值d(va,v)+w(vv),并将其与此前纪录的最短路的长l(v)进行比较即 可,而不必对所有的点v∈S都重新计算d(v,v)+v(vv)且比较出一个最小的,从而避 免了重复计算和比较 按照算法过程,标号法实现算法主要包括两个过程,(1)修改各点的标号,(2)从S的 所有点中取标号最小的一个点,放入S中。某个点被放入S集合后,它的标号成为永久标 号,不再被修改。算法反复执行上述过程,直至所有顶点获得永久标号(被放入S中)。 算法具体步骤如下 Dijkstra算法:求非负权图中w点到其余各点的最短路。 第1步.令l(v)=0,l(v)三∞,(ν≠v0),S:={v0},S=F\S,i:=0。 第2步.对每个ν∈S,令l(v)=min{(v),l(v)+w(vv)}。 取γ*∈S使得l(*)=min{l(v)}。记v1=v*,令S:=S∪{},S=V\S。 第3步.令i:=i+1。如果i=υ-1,则停止:否则,转第2步。 3.算法正确性 定理121 Dijkstra算法结束时,对任一个顶点v,其标号l)恰是v到v的最短路的长。 证明:按照算法,顶点ν的最终标号v)是ν进入集合S时的标号。假设ν在算法第i次循 环时进入集合S,则v=V1,且v进入集合S后S={v,v12…,v,v4}。由于lv)是算法在 前i次循环中逐次比较出的当前从vo到v最短路的长,因此从vo到v仅含{v,v1…v1,v1} 中点的任何路的长都不会小于l()。任取图G中一条从v到v的路P,如果P仅含 {va,v1,…,v,v1}中的点,则如上所述,P的长不会小于;如果P含{va,v1,…,V2v1} 之外的点,无妨设沿着P从v出发第一个不在{v,v1,…,v,Va1}中的顶点是v。因在算法 第i次循环时,v+1进入S而v仍未进入S,说明当前lv*)≤lv′)。注意v′只是P的中途 点且图G中所有边的权都非负,而当前的/v)大于或等于v到v’仅含{v,v13…,v,V1}中 点的最短路的长,故路P的长大于或等于P上w到v段的长(≥l(v),从而P的长不会小 于l(v+1)(即(v)。证毕。 按照上述定理, Dijkstra算法结束时,每个顶点的标号l(v)表示v到该点的最短路的长 此外,通过检查标号的来源点,可反向追踪得到v到各点的最短路。 4.算法有效性 对于一个图论算法,如果在任何图上施行这个算法所需要的基本计算量(比如加、减
11 标号法的基本原理是累进比较。初始时， 0 l v( ): 0 = ，l(v) := ∞ ，（ 0 v v ≠ ）， 0 S v = { }， S VS = \ 。然后算法逐步修改 S 中顶点的标号。第 i 步时，对 S 中每个v ，只对刚进入 S 的点 vi 计算 0 (,) ( ) i i d v v w vv + （即 () ( ) i i l v w vv + ），并与l v( ) 进行比较，取其较小的一个 作为的新标号，即 ( ) : min{ ( ), ( ) ( )} i i l v l v l v w vv = + 。因为对在 i v 之前进入 S 的点 01 1 ,, , i vv v " − ， 0 (, ) ( ) k k dv v wvv + （k = 1, 2, …, i−1）的值及其大小信息已含于l v( ) 之中， 因此只需计算一个值 0 (,) ( ) i i d v v w vv + ，并将其与此前纪录的最短路的长l v( ) 进行比较即 可，而不必对所有的点 i v S ∈ 都重新计算 0 (,) ( ) i i d v v w vv + 且比较出一个最小的，从而避 免了重复计算和比较。 按照算法过程，标号法实现算法主要包括两个过程，（1）修改各点的标号，（2）从 S 的 所有点中取标号最小的一个点，放入 S 中。某个点被放入 S 集合后，它的标号成为永久标 号，不再被修改。算法反复执行上述过程，直至所有顶点获得永久标号（被放入 S 中）。 算法具体步骤如下： Dijkstra 算法：求非负权图中 v0 点到其余各点的最短路。 第 1 步. 令 0 l v( ): 0 = ，l(v) := ∞ ，（ 0 v v ≠ ）， 0 S v :{} = , S VS : \ = ，i := 0 。 第 2 步. 对每个v S ∈ ，令 ( ) : min{ ( ), ( ) ( )} i i l v l v l v w vv = + 。 取v S *∈ 使得 ( *) min{ ( )} v S lv lv ∈ = 。记 * i 1 v v + = , 令 1 : {} i SS v = ∪ + , S VS : \ = 。 第 3 步. 令i := i + 1。如果i = − υ 1, 则停止；否则，转第 2 步。 3. 算法正确性 定理 1.2.1 Dijkstra 算法结束时，对任一个顶点 v，其标号 l(v)恰是 v0到 v 的最短路的长。 证明：按照算法，顶点 v 的最终标号 l(v)是 v 进入集合 S 时的标号。假设 v 在算法第 i 次循 环时进入集合 S，则 i 1 v v = + ，且 v 进入集合 S 后 {, , ,, } 01 1 i i S vv vv = " + 。由于 l(v)是算法在 前 i 次循环中逐次比较出的当前从 v0到 v 最短路的长，因此从 v0 到 v 仅含{, , ,, } 01 1 i i vv vv " + 中点的任何路的长都不会小于 l(v)。任取图 G 中一条从 v0 到 v 的路 P，如果 P 仅含 {, , ,, } 01 1 i i vv vv " + 中的点，则如上所述，P 的长不会小于 l(v)；如果 P 含{, , ,, } 01 1 i i vv vv " + 之外的点，无妨设沿着 P 从 v0 出发第一个不在{, , ,, } 01 1 i i vv vv " + 中的顶点是 v′。因在算法 第 i 次循环时，vi+1 进入 S 而 v′ 仍未进入 S，说明当前 l(vi+1)≤ l(v′ )。注意 v′ 只是 P 的中途 点且图 G 中所有边的权都非负，而当前的 l(v′ )大于或等于 v0到 v′ 仅含{, , ,, } 01 1 i i vv vv " + 中 点的最短路的长，故路 P 的长大于或等于 P 上 v0到 v′ 段的长（≥ l(v′ )），从而 P 的长不会小 于 l(vi+1)（即 l(v)）。 证毕。 按照上述定理，Dijkstra 算法结束时，每个顶点的标号 l(v)表示 v0 到该点的最短路的长。 此外，通过检查标号的来源点，可反向追踪得到 v0 到各点的最短路。 4. 算法有效性 对于一个图论算法，如果在任何图上施行这个算法所需要的基本计算量（比如加、减
乘、除运算或比较、赋值等)都以图的顶点数υ的一个函数为其上界,则称这个函数为该算 法的计算复杂度或时间复杂度,一般简称为复杂度( complexity)。图的顶点数U称为图论问 题的规模。人们总是希望利用计算机执行算法以解决人工难以计算的大规模问题,因此,对 个算法人们主要关心它在解决大规模问题时的计算量。对于图论算法,主要关心当图的顶 点数υ增大时,算法所需计算量的增加情况。如果一个算法的计算复杂度是规模υ的指数函 数,比如2°、υ!等,则当问题的规模较大时,算法所需的计算量快速增大以至于无法接受, 这样的算法在解决大规模问题时实际上是无用的。当一个算法的计算复杂度是多项式函数 时,算法的计算量随规模的增加其增幅较缓,人们认为一般是可以接受的。因此,一个具有 多项式时间复杂度的算法称为是有效算法( efficient algorithm)或好算法( good algorithm), 有时直接称为多项式时间算法或多项式算法。对于多项式算法,影响其时间复杂度的主项是 多项式的最高次项,因此人们在作算法分析时,主要关注其最高次项。一般地,如果一个算 法的复杂度是a2U3+aυ-1+…+aU+a0,则我们说它的计算复杂度是O(U),或是 O(U3)阶的。利用这个记号,如果一个算法的复杂度是2或b!,我们也可写为O2")或 O(o!) 按照复杂度的上述定义,如果一个算法是OU)阶的,则它也是O(U4)阶的,甚至也 是O(20)阶的。但实际上,人们在提到算法的复杂性时,总是指它的最低的阶。 下一定理表明 Dijkstra算法是多项式算法。 定理122 Dijkstra算法的计算复杂度为O(u2)。 证明; Dijkstra算法的主要计算量在第2步。在第i次循环中,第2步第1式需要υ-i-1次 加法,υ-1-1次比较:第2式需要不超过U-i-1次比较。(i=0,1,…,U-2)。从而U-1 次循环总的计算量不超过∑3(U-1-1)= 3U(U-1) 对一个需要用算法解决的问题,如果存在求解它的多项式算法,则这个问题称为P问 题( polynomial problem)。如果一个问题,当猜出其答案时可在多项式计算量内验证答案的正 确性,则这个问题称为NP问题(non- deterministic polynomial problem)。将所有P问题的集合 记为P,所有NP问题的集合记为NP,是否P=NP?这是计算机科学和组合最优化领域的 个重要未解难题。明显地PcNP,但人们目前还不知道是否P→NP。Cook(1970)发现 NP问题中有一类问题,只要其中有一个问题是P问题,则所有NP问题全是P问题,即 P=NP。这类问题称为NP完全问题,简称为NPC问题( non-deterministic polynomial problem)。 遗憾的是,对目前己找到的成千上万个NPC问题,人们还未能证明其中任何一个是P问题。 图论中有许多问题属于NPC问题。有兴趣的读者可参阅下列文献 2]http://www.nada.kth.se/-viggo/problemlist/ 3]M.R. Garey D. S. Johnson, Computers and Intractability a guid to the theory of NP-completeness, V.H. Freedman, San francisco,1979.(中译本:张立昂等译,计算机和难 解性一NP完全性理论导引,科学出版社,1987)。 [4 D.S. Hochbaum, Approximation algorithms for NP-hard problems, International Thomson
12 乘、除运算或比较、赋值等）都以图的顶点数υ 的一个函数为其上界，则称这个函数为该算 法的计算复杂度或时间复杂度，一般简称为复杂度（complexity）。图的顶点数υ 称为图论问 题的规模。人们总是希望利用计算机执行算法以解决人工难以计算的大规模问题，因此，对 一个算法人们主要关心它在解决大规模问题时的计算量。对于图论算法，主要关心当图的顶 点数υ 增大时，算法所需计算量的增加情况。如果一个算法的计算复杂度是规模υ 的指数函 数，比如2υ 、υ !等，则当问题的规模较大时，算法所需的计算量快速增大以至于无法接受， 这样的算法在解决大规模问题时实际上是无用的。当一个算法的计算复杂度是多项式函数 时，算法的计算量随规模的增加其增幅较缓，人们认为一般是可以接受的。因此，一个具有 多项式时间复杂度的算法称为是有效算法（efficient algorithm）或好算法(good algorithm）， 有时直接称为多项式时间算法或多项式算法。对于多项式算法，影响其时间复杂度的主项是 多项式的最高次项，因此人们在作算法分析时，主要关注其最高次项。一般地，如果一个算 法的复杂度是 1 1 10 k k k k a a aa υυ υ − + − ++ + " ，则我们说它的计算复杂度是 ( ) k O υ ，或是 ( ) k O υ 阶的。利用这个记号，如果一个算法的复杂度是 2υ 或υ !，我们也可写为O(2 ) υ 或 O( !) υ 。 按照复杂度的上述定义，如果一个算法是 ( ) k O υ 阶的，则它也是 1 ( ) k O υ + 阶的，甚至也 是O(2 ) υ 阶的。但实际上，人们在提到算法的复杂性时，总是指它的最低的阶。 下一定理表明 Dijkstra 算法是多项式算法。 定理 1.2.2 Dijkstra 算法的计算复杂度为 ( ) 2 O υ 。 证明：Dijkstra 算法的主要计算量在第 2 步。在第 i 次循环中，第 2 步第 1 式需要υ − −i 1次 加法，υ − −i 1次比较；第 2 式需要不超过υ − i −1次比较。(i = 0,1, , 2 " υ − )。从而υ −1 次循环总的计算量不超过 2 0 3( 1) i i ν υ − = ∑ −− = 3 ( 1) 2 υ υ − = ( ) 2 O υ 。 对一个需要用算法解决的问题，如果存在求解它的多项式算法，则这个问题称为 P 问 题(polynomial problem)。如果一个问题，当猜出其答案时可在多项式计算量内验证答案的正 确性，则这个问题称为 NP 问题(non-deterministic polynomial problem)。将所有 P 问题的集合 记为 P，所有 NP 问题的集合记为 NP，是否 P=NP？这是计算机科学和组合最优化领域的一 个重要未解难题。明显地 P NP ⊆ ，但人们目前还不知道是否 P NP ⊇ 。Cook(1970)发现 NP 问题中有一类问题，只要其中有一个问题是 P 问题，则所有 NP 问题全是 P 问题，即 P=NP 。这类问题称为NP完全问题，简称为NPC问题(non-deterministic polynomial problem)。 遗憾的是，对目前已找到的成千上万个 NPC 问题，人们还未能证明其中任何一个是 P 问题。 图论中有许多问题属于 NPC 问题。有兴趣的读者可参阅下列文献。 [2] http://www.nada.kth.se/~viggo/problemlist/ [3] M. R. Garey & D. S. Johnson, Computers and Intractability − a guid to the theory of NP-completeness, W. H. Freedman, San Francisco, 1979. （中译本：张立昂等译，计算机和难 解性—NP 完全性理论导引，科学出版社，1987）。 [4] D.S. Hochbaum, Approximation algorithms for NP-hard problems, International Thomson