单源最短路径[贪婪算法应用]

在这个问题中，给出有向图G，它的每条边都有一个非负的长度（耗费） a [i ][ j ]，路径的长度即为此路径所经过的边的长度之和。对于给定的源顶点s，需找出从它到图中其他任意顶点（称为目的）的最短路径。图13-10a 给出了一个具有五个顶点的有向图，各边上的数即为长度。假设源顶点s 为1，从顶点1出发的最短路径按路径长度顺序列在图13-10b 中，每条路径前面的数字为路径的长度。

利用E. Dijkstra发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点。也就是说， D i j k s t r a的方法按路径长度顺序产生最短路径。

首先最初产生从s 到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，产生下一个最短路径。一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产生的最短路径加上一条边。这种策略并不总是起作用。另一种方法是在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些边中先选择最短的，这种策略即是D i j k s t r a算法。

可以验证按长度顺序产生最短路径时，下一条最短路径总是由一条已产生的最短路径加上一条边形成。实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。例如在图1 3 - 1 0中，b 中第二条路径是第一条路径扩充一条边形成的；第三条路径则是第二条路径扩充一条边；第四条路径是第一条路径扩充一条边；第五条路径是第三条路径扩充一条边。

通过上述观察可用一种简便的方法来存储最短路径。可以利用数组p，p [ i ]给出从s 到达i的路径中顶点i 前面的那个顶点。在本例中p [ 1 : 5 ] = [ 0 , 1 , 1 , 3 , 4 ]。从s 到顶点i 的路径可反向创建。从i 出发按p[i],p[p[i]],p[p[p[i]]], .的顺序，直到到达顶点s 或0。在本例中，如果从i = 5开始，则顶点序列为p[i]=4, p[4]=3, p[3]=1=s，因此路径为1 , 3 , 4 , 5。

为能方便地按长度递增的顺序产生最短路径，定义d [ i ]为在已产生的最短路径中加入一条最短边的长度，从而使得扩充的路径到达顶点i。最初，仅有从s 到s 的一条长度为0的路径，这时对于每个顶点i，d [ i ]等于a [ s ] [ i ]（a 是有向图的长度邻接矩阵）。为产生下一条路径，需要选择还未产生最短路径的下一个节点，在这些节点中d值最小的即为下一条路径的终点。当获得一条新的最短路径后，由于新的最短路径可能会产生更小的d值，因此有些顶点的d值可能会发生变化。

综上所述，可以得到图1 3 - 11所示的伪代码， 1) 将与s 邻接的所有顶点的p 初始化为s，这个初始化用于记录当前可用的最好信息。也就是说，从s 到i 的最短路径，即是由s到它自身那条路径再扩充一条边得到。当找到更短的路径时， p [ i ]值将被更新。若产生了下一条最短路径，需要根据路径的扩充边来更新d 的值。

1) 初始化d[i ] =a[s] [i ]（1≤i≤n），

对于邻接于s的所有顶点i，置p[i ] =s, 对于其余的顶点置p[i ] = 0；

对于p[i]≠0的所有顶点建立L表。

2) 若L为空，终止，否则转至3 )。

3) 从L中删除d值最小的顶点。

4) 对于与i 邻接的所有还未到达的顶点j，更新d[ j ]值为m i n{d[ j ], d[i ] +a[i ][ j ] }；若d[ j ]发生了变化且j 还未

在L中，则置p[ j ] = 1，并将j 加入L，转至2。

图1 - 11 最短路径算法的描述

1. 数据结构的选择

我们需要为未到达的顶点列表L选择一个数据结构。从L中可以选出d 值最小的顶点。如果L用最小堆（见9 . 3节）来维护，则这种选取可在对数时间内完成。由于3) 的执行次数为O ( n )，所以所需时间为O ( n l o g n )。由于扩充一条边产生新的最短路径时，可能使未到达的顶点产生更小的d 值，所以在4) 中可能需要改变一些d 值。虽然算法中的减操作并不是标准的最小堆操作，但它能在对数时间内完成。由于执行减操作的总次数为： O(有向图中的边数)= O ( n2 )，因此执行减操作的总时间为O ( n2 l o g n )。

若L用无序的链表来维护，则3) 与4) 花费的时间为O ( n2 )，3) 的每次执行需O(|L | ) =O( n )的时间，每次减操作需( 1 )的时间（需要减去d[j] 的值，但链表不用改变）。利用无序链表将图1 - 11的伪代码细化为程序1 3 - 5，其中使用了C h a i n (见程序3 - 8 )和C h a i n I t e r a t o r类（见程序3 - 1 8）。

程序13-5 最短路径程序

template<class T>

void AdjacencyWDigraph<T>::ShortestPaths(int s, T d[], int p[])

{// 寻找从顶点s出发的最短路径, 在d中返回最短距离

// 在p中返回前继顶点

if (s < 1 || s > n) throw OutOfBounds();

Chain<int> L; // 路径可到达顶点的列表

ChainIterator<int> I;

// 初始化d, p, L

for (int i = 1; i <= n; i++){

d[i] = a[s][i];

if (d[i] == NoEdge) p[i] = 0;

else {p[i] = s;

L . I n s e r t ( 0 , i ) ; }

}

// 更新d, p

while (!L.IsEmpty()) {// 寻找具有最小d的顶点v

int *v = I.Initialize(L);

int *w = I.Next();

while (w) {

if (d[*w] < d[*v]) v = w;

w = I.Next();}

// 从L中删除通向顶点v的下一最短路径并更新d

int i = *v;

L . D e l e t e ( * v ) ;

for (int j = 1; j <= n; j++) {

if (a[i][j] != NoEdge && (!p[j] ||

d[j] > d[i] + a[i][j])) {

// 减小d [ j ]

d[j] = d[i] + a[i][j];

// 将j加入L

if (!p[j]) L.Insert(0,j);

p[j] = i;}

}

}

}

若N o E d g e足够大，使得没有最短路径的长度大于或等于N o E d g e，则最后一个for 循环的i f条件可简化为：if (d[j] > d[i] + a[i][j])) NoEdge 的值应在能使d[j]+a[i][j] 不会产生溢出的范围内。

2. 复杂性分析

程序1 3 - 5的复杂性是O ( n2 )，任何最短路径算法必须至少对每条边检查一次，因为任何一条边都有可能在最短路径中。因此这种算法的最小可能时间为O ( e )。由于使用耗费邻接矩阵来描述图，仅决定哪条边在有向图中就需O ( n2 )的时间。因此，采用这种描述方法的算法需花费O ( n2 )的时间。不过程序1 3 - 5作了优化（常数因子级）。即使改变邻接表，也只会使最后一个f o r循环的总时间降为O ( e )（因为只有与i 邻接的顶点的d 值改变）。从L中选择及删除最小距离的顶点所需总时间仍然是O( n2 )。

二分图是一个无向图，它的n 个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A' 覆盖集合B（或简单地说，A' 是一个覆盖）。覆盖A' 的大小即为A' 中的顶点数目。当且仅当A' 是覆盖B的子集中最小的时，A' 为最小覆盖。

例1-10 考察如图1 - 6所示的具有1 7个顶点的二分图，A={1, 2, 3, 16, 17}和B={4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15}，子集A' = { 1 , 1 6 , 1 7 }是B的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖（ b i p a r t i t e - c o v e r）问题。在例1 2 - 3中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的翻译人员进行翻译”这一类的问题。

二分覆盖问题类似于集合覆盖（ s e t - c o v e r）问题。在集合覆盖问题中给出了k 个集合S= {S1 , S2 ,., Sk }，每个集合Si 中的元素均是全集U中的成员。当且仅当èi S'Si =U时，S的子集S' 覆盖U，S '中的集合数目即为覆盖的大小。当且仅当没有能覆盖U的更小的集合时，称S' 为最小覆盖。可以将集合覆盖问题转化为二分覆盖问题（反之亦然），即用A的顶点来表示S1 , ., Sk ，B中的顶点代表U中的元素。当且仅当S的相应集合中包含U中的对应元素时，在A与B的顶点之间存在一条边。

例1 - 11 令S= {S1，. . .，S5 }, U= { 4，5，. . .，15}, S1 = { 4，6，7，8，9，1 3 }，S2 = { 4，5，6，8 }，S3 = { 8，1 0，1 2，1 4，1 5 }，S4 = { 5，6，8，1 2，1 4，1 5 }，S5 = { 4，9，1 0，11 }。S ' = {S1，S4，S5 }是一个大小为3的覆盖，没有更小的覆盖， S' 即为最小覆盖。这个集合覆盖问题可映射为图1-6的二分图，即用顶点1，2，3，1 6和1 7分别表示集合S1，S2，S3，S4 和S5，顶点j 表示集合中的元素j，4≤j≤1 5。

集合覆盖问题为N P-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是N P-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A' ，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。

例1-12 考察图1 - 6所示的二分图，初始化A' = 且B中没有顶点被覆盖，顶点1和1 6均能覆盖B中的六个顶点，顶点3覆盖五个，顶点2和1 7分别覆盖四个。因此，在第一步往A' 中加入顶点1或1 6，若加入顶点1 6，则它覆盖的顶点为{ 5 , 6 , 8 , 1 2 , 1 4 , 1 5 }，未覆盖的顶点为{ 4 , 7 , 9 , 1 0 , 11 , 1 3 }。顶点1能覆盖其中四个顶点（ { 4 , 7 , 9 , 1 3 }），顶点2 覆盖一个( { 4 } )，顶点3覆盖一个（{ 1 0 }），顶点1 6覆盖零个，顶点1 7覆盖四个{ 4 , 9 , 1 0 , 11 }。下一步可选择1或1 7加入A' 。若选择顶点1，则顶点{ 1 0 , 11} 仍然未被覆盖，此时顶点1，2，1 6不覆盖其中任意一个，顶点3覆盖一个，顶点1 7覆盖两个，因此选择顶点1 7，至此所有顶点已被覆盖，得A' = { 1 6 , 1 , 1 7 }。

图1 - 7给出了贪婪覆盖启发式方法的伪代码，可以证明： 1) 当且仅当初始的二分图没有覆盖时，算法找不到覆盖；2) 启发式方法可能找不到二分图的最小覆盖。

2. 降低复杂性

通过使用有序数组N e wi、最大堆或最大选择树（max selection tree）可将每步选取顶点v的复杂性降为( 1 )。但利用有序数组，在每步的最后需对N e wi 值进行重新排序。若使用箱子排序，则这种排序所需时间为(S i z e O f B ) ( S i z e O fB =|B| ) （见3 . 8 . 1节箱子排序）。由于一般S i z e O f B比S i z e O f A大得多，因此有序数组并不总能提高性能。

如果利用最大堆，则每一步都需要重建堆来记录N e w值的变化，可以在每次N e w值减1时进行重建。这种减法操作可引起被减的N e w值最多在堆中向下移一层，因此这种重建对于每次N e w值减1需( 1 )的时间，总共的减操作数目为O (e)。因此在算法的所有步骤中，维持最大堆仅需O (e)的时间，因而利用最大堆时覆盖算法的总复杂性为O (n2 )或O (n+e)。

若利用最大选择树，每次更新N e w值时需要重建选择树，所需时间为(log S i z e O f A)。重建的最好时机是在每步结束时，而不是在每次N e w值减1时，需要重建的次数为O (e)，因此总的重建时间为O (e log S i z e OfA)，这个时间比最大堆的重建时间长一些。然而，通过维持具有相同N e w值的顶点箱子，也可获得和利用最大堆时相同的时间限制。由于N e w的取值范围为0到S i z e O f B，需要S i z e O f B+ 1个箱子，箱子i 是一个双向链表，链接所有N e w值为i 的顶点。在某一步结束时，假如N e w [ 6 ]从1 2变到4，则需要将它从第1 2个箱子移到第4个箱子。利用模拟指针及一个节点数组n o d e（其中n o d e [ i ]代表顶点i，n o d e [ i ] . l e f t和n o d e [ i ] . r i g h t为双向链表指针），可将顶点6从第1 2个箱子移到第4个箱子，从第1 2个箱子中删除n o d e [ 0 ]并将其插入第4个箱子。利用这种箱子模式，可得覆盖启发式算法的复杂性为O (n2 )或O(n+e)。（取决于利用邻接矩阵还是线性表来描述图）。

3. 双向链接箱子的实现

为了实现上述双向链接箱子，图1 - 9定义了类U n d i r e c t e d的私有成员。N o d e Ty p e是一个具有私有整型成员l e f t和r i g h t的类，它的数据类型是双向链表节点，程序1 3 - 3给出了U n d i r e c t e d的私有成员的代码。

void CreateBins (int b, int n)

创建b个空箱子和n个节点

void DestroyBins() { delete [] node;

delete [] bin;}

void InsertBins(int b, int v)

在箱子b中添加顶点v

void MoveBins(int bMax, int ToBin, int v)

从当前箱子中移动顶点v到箱子To B i n

int *bin;

b i n [ i ]指向代表该箱子的双向链表的首节点

N o d e Type *node;

n o d e [ i ]代表存储顶点i的节点

图1-9 实现双向链接箱子所需的U n d i r e c t e d私有成员

程序13-3 箱子函数的定义

void Undirected::CreateBins(int b, int n)

{// 创建b个空箱子和n个节点

node = new NodeType [n+1];

bin = new int [b+1];

// 将箱子置空

for (int i = 1; i <= b; i++)

bin[i] = 0;

}

void Undirected::InsertBins(int b, int v)

{// 若b不为０，则将v 插入箱子b

if (!b) return; // b为0，不插入

node[v].left = b; // 添加在左端

if (bin[b]) node[bin[b]].left = v;

node[v].right = bin[b];

bin[b] = v;

}

void Undirected::MoveBins(int bMax, int ToBin, int v)

{// 将顶点v 从其当前所在箱子移动到To B i n .

// v的左、右节点

int l = node[v].left;

int r = node[v].right;

// 从当前箱子中删除

if (r) node[r].left = node[v].left;

if (l > bMax || bin[l] != v) // 不是最左节点

node[l].right = r;

else bin[l] = r; // 箱子l的最左边

// 添加到箱子To B i n

I n s e r t B i n s ( ToBin, v);

}

函数C r e a t e B i n s动态分配两个数组： n o d e和b i n，n o d e [i ]表示顶点i, bin[i ]指向其N e w值为i的双向链表的顶点, f o r循环将所有双向链表置为空。如果b≠0，函数InsertBins 将顶点v 插入箱子b 中。因为b 是顶点v 的New 值，b = 0意味着顶点v 不能覆盖B中当前还未被覆盖的任何顶点，所以，在建立覆盖时这个箱子没有用处，故可以将其舍去。当b≠0时，顶点n 加入New 值为b 的双向链表箱子的最前面，这种加入方式需要将node[v] 加入bin[b] 中第一个节点的左边。由于表的最左节点应指向它所属的箱子，因此将它的node[v].left 置为b。若箱子不空，则当前第一个节点的left 指针被置为指向新节点。node[v] 的右指针被置为b i n [ b ]，其值可能为0或指向上一个首节点的指针。最后， b i n [ b ]被更新为指向表中新的第一个节点。MoveBins 将顶点v 从它在双向链表中的当前位置移到New 值为ToBin 的位置上。其中存在bMa x，使得对所有的箱子b i n[ j ]都有：如j>bMa x，则b i n [ j ]为空。代码首先确定n o d e [ v ]在当前双向链表中的左右节点，接着从双链表中取出n o d e [ v ]，并利用I n s e r t B i n s函数将其重新插入到b i n [ To B i n ]中。

4. Undirected::BipartiteCover的实现

函数的输入参数L用于分配图中的顶点（分配到集合A或B）。L [i ] = 1表示顶点i在集合A中，L[ i ] = 2则表示顶点在B中。函数有两个输出参数： C和m，m为所建立的覆盖的大小， C [ 0 , m - 1 ]是A中形成覆盖的顶点。若二分图没有覆盖，函数返回f a l s e；否则返回t r u e。完整的代码见程序1 3 - 4。

程序13-4 构造贪婪覆盖

bool Undirected::BipartiteCover(int L[], int C[], int& m)

{// 寻找一个二分图覆盖

// L 是输入顶点的标号, L[i] = 1 当且仅当i 在Ａ中

// C 是一个记录覆盖的输出数组

// 如果图中不存在覆盖，则返回f a l s e

// 如果图中有一个覆盖，则返回t r u e ;

// 在m中返回覆盖的大小; 在C [ 0 : m - 1 ]中返回覆盖

int n = Ve r t i c e s ( ) ;

// 插件结构

int SizeOfA = 0;

for (int i = 1; i <= n; i++) // 确定集合A的大小

if (L[i] == 1) SizeOfA++;

int SizeOfB = n - SizeOfA;

CreateBins(SizeOfB, n);

int *New = new int [n+1]; / /顶点i覆盖了Ｂ中N e w [ i ]个未被覆盖的顶点

bool *Change = new bool [n+1]; // Change[i]为t r u e当且仅当New[i] 已改变

bool *Cov = new bool [n+1]; // Cov[i] 为true 当且仅当顶点i 被覆盖

I n i t i a l i z e P o s ( ) ;

LinkedStack<int> S;

// 初始化

for (i = 1; i <= n; i++) {

Cov[i] = Change[i] = false;

if (L[i] == 1) {// i 在A中

New[i] = Degree(i); // i 覆盖了这么多

InsertBins(New[i], i);}}

// 构造覆盖

int covered = 0, // 被覆盖的顶点

MaxBin = SizeOfB; // 可能非空的最大箱子

m = 0; // C的游标

while (MaxBin > 0) { // 搜索所有箱子

// 选择一个顶点

if (bin[MaxBin]) { // 箱子不空

int v = bin[MaxBin]; // 第一个顶点

C[m++] = v; // 把v 加入覆盖

// 标记新覆盖的顶点

int j = Begin(v), k;

while (j) {

if (!Cov[j]) {// j尚未被覆盖

Cov[j] = true;

c o v e r e d + + ;

// 修改N e w

k = Begin(j);

while (k) {

New[k]--; // j 不计入在内

if (!Change[k]) {

S.Add(k); // 仅入栈一次

Change[k] = true;}

k = NextVe r t e x ( j ) ; }

}

j = NextVe r t e x ( v ) ; }

// 更新箱子

while (!S.IsEmpty()) {

S . D e l e t e ( k ) ;

Change[k] = false;

MoveBins(SizeOfB, New[k], k);}

}

else MaxBin--;

}

D e a c t i v a t e P o s ( ) ;

D e s t r o y B i n s ( ) ;

delete [] New;

delete [] Change;

delete [] Cov;

return (covered == SizeOfB);

}