, 张媛媛4, 刘善军21. 北京师范大学 减灾与应急管理研究院, 北京 100875;
2. 东北大学 资源与土木工程学院, 辽宁 沈阳 110819;
3. 中南大学 地球科学与信息物理学院, 湖南 长沙 410083;
4. 中国矿业大学(北京) 地球科学与测绘工程学院, 北京 100083
收稿日期：2016-04-29
基金项目：国家高技术研究发展计划项目(2011AA120302)。
作者简介：江锦成(1989-), 男，江西九江人，北京师范大学博士研究生;
吴立新(1966-)，男，江西宜春人，东北大学教授，博士生导师，教育部“****奖励计划”特聘教授;
刘善军(1965-)，男，河北涿鹿人，东北大学教授，博士生导师。
摘要：为提升大规模网络全源最短路径的求解效率, 基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性; 在已知单源最短路径树的基础上, 基于重优化理论实现了异源最短路径树间的高效转换, 进而得出高效求解全源最短路径的RASP算法; 理论证明RASP算法的时间复杂度为O(3n2+2nm).实验测试表明:无论是在稀疏还是稠密网络上, RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.
关键词：重优化全源最短路径大规模网络Floyd算法Dijkstra算法
A Reoptimization-Based All-Pairs Shortest Path Algorithm for Large-Scale Network—RASP Algorithm
JIANG Jin-cheng1, WU Li-xin2,3
, ZHANG Yuan-yuan4, LIU Shan-jun21. Academy of Disaster Reduction and Emergency Management, Beijing Normal University, Beijing 100875, China;
2. School of Resources & Civil Engineering, Northeastern University, Shenyang 110819, China;
3. School of Geoscience and Info-Physics, Central South University, Changsha 410083, China;
4. College of Geoscience and Surveying Engineering, China University of Mining & Technology, Beijing 100083, China
Corresponding author: WU Li-xin, E-mail:awulixin@263.net
Abstract: In order to improve the computational performance of searching all-pairs shortest paths in a large-scale network, an exact all-pairs shortest path method—RASP algorithm is proposed based on the reoptimization theory. First, the correlation and difference between the shortest path trees with different sources are analyzed. Second, the efficient conversion from a known single-source shortest path tree to another one with different source is achieved based on the reoptimization-based theory. Furthermore, the reoptimization-based all-pairs shortest path (RASP) algorithm utilizes this conversion method to calculate efficiently all-pairs shortest paths. At last, the time complexity of RASP algorithm is proved to be O(3n2+2nm). The experimental test demonstrates that RASP algorithm gains the advantage over Floyd, n-Dijkstra algorithms and their improved algorithms in both sparse and dense networks.
Key Words: reoptimizationall-pairsshortest pathlarge-scale networkFloyd algorithmDijkstra algorithm
作为图论的经典问题, 最短路径在诸多领域都有着广泛的应用, 如:智能交通系统[1]、地理信息系统[2-4]、计算机网络与通讯[5]等.为提升算法的计算效率或满足特定的应用需求, 已有大量优秀算法[6-8]被提出.按照解的精度, 最短路径算法可分为精确和近似算法; 按照求解目标的数量, 最短路径问题又可分为单源和全(多)源最短路径.本文的研究对象是精确全源最短路径问题, 即旨在求解所有点对之间的精确最短路径.
目前, 求解全源最短路径问题的典型算法包括Floyd算法[9]和多次Dijkstra算法[10].其中, Floyd算法的时间复杂度为O(n3); Dijkstra算法是单源最短路径算法, 其时间复杂度为O(n2).为获得全源最短路径, 需执行n次, 故总复杂度为O(n3).由此可见, 全源最短路径算法的时间复杂度依然很高, 难以满足现有大规模网络或实时计算的要求.为进一步提升算法的计算效率, 除设计低复杂度的高效算法外, 还有学者[11]采用并行计算技术来加速全源最短路径问题的求解, 但并行计算不能减少总的计算量.
重优化方法的基本思想是充分利用异源最短路径树间的相关性, 避免重复计算, 从而达到高效求解全源最短路径的目的.该方法是在已有最短路径树的基础上, 针对网络的动态变化而对路径进行重新调整的过程.目前, 其已被用于解决动态最短路径问题, 如单边权重变化、多边权重变化[12], 以及源点变化[13]等情景.由于仅计算最短路径可能发生变化的节点, 故重优化方法能有效减小搜索空间, 提升求解速度.其中, 确定最小搜索空间以及分析最短路径的变化规律是重优化方法的两个重要内容.本文首先分析源点发生变化时, 异源最短路径树间的相关性与差异性, 并依此设计高效的转换方法; 随后将该方法扩展至全源最短路径问题的求解.
1 相关工作将现实网络抽象成无向图G(V, E, W), 其中V为节点集合, E为边集合, W为权重集合, n=|V|为节点数量, m=|E|为边数量.对任意一条边(i, j) ∈E, i∈V, j∈V分别为边(i, j)的两个端点, w(i, j)∈W表示网络边(i, j)的权重.单源最短路径问题是求解从起始点s(或所有点)到终点t具有最小总权重的最短路径.全源最短路径则是求解所有点对间的最短路径.通常, 赋予每个节点i一对标号(di, pi), 其中di表示i到t的最短距离, pi表示最短路径上i的前驱节点, d(i, j)表示节点i和j间的距离.
Dijkstra算法是求解单源最短路径最常用的方法, 其主要步骤包括:1) 将V分解成S和T, 设置S={s}, T=V-S, ds=0, di=∞, ?i∈V/s; 2) 搜索T中距离S最近的节点j, 计算dj; 3) 设置S=S∪{j}, T=T-{j}; 4) 若T=?或t∈S, 算法终止; 否则转至步骤2).
Floyd算法是一种动态规划算法, 适用于求解全源最短路径, 主要步骤包括:1) 初始化任意点对(i, j)间的距离, d(i, j)=w(i, j); 若(i, j)?E, 则d(i, j)=∞; 2) 对任意点对(u, v), 检查是否存在节点x使得d(u, x)+d(x, v) < d(u, v), 若存在则设置d(u, v)=d(u, x)+d(x, v); 3) 重复步骤2) 至所有点对间的距离都满足最优条件.
2 异源最短路径树当Dijkstra算法计算出网络所有节点到目的节点t的最短路径后, 可生成一棵最短路径树(见图 1a).对于相邻的目的节点t1和t2, 其对应的两棵异源最短路径树T(t1)和T(t2)存在着很大的相关性.本文以图 1为例, 分析两棵异源最短路径树间的相关性与差异性.
图 1(Fig. 1)
 | 图 1 异源最短路径树实例Fig.1 An example of the shortest path tree with different sources (a)—原始网络；(b)—最短路径树T(v10); (c)—最短路径树T(v7). |
如图 1b所示, T(v10)包含3棵子树:T′(v7)，T′(v8)和T′(v9).为方便表达, T(v7)表示图 1b中以v7为根节点的子树, T′(v7)则为图 1c中以v7为根节点的最短路径树.对任意节点i, di表示在T(v10)中i到v10的最短距离, 而d′i则表示在T′(v7)中i到v7的最短距离, d(i, j)表示节点i与j间的最短距离.对比图 1b和图 1c可知:
1) 子树T′(v7)的结构保持不变, 但其上所有点的最短距离全部减少2.
证明??对于任意节点i∈T′(v7), di=d(i, v10)=d(i, v7)+d(v7, v10), 而d′i=d(i, v7)=di-d(v7, v10).由于d(v7, v10)是全局最短距离, 为固定常量, 故T′(v7)上所有点的最短距离都减少d(v7, v10)=2, 结构保持不变.
2) 对任意节点j∈T(v10)-T′(v7), 都存在|d′j-dj|≤d(v7, v10).
证明??在T(v7)中, 必存在一条路径P(j, v7)=P(j, v10)+P(v10, v7).而在T′(v7)中, 必有d′j=d(j, v7) ≤d(j, v10)+d(v10, v7), 故d′j-dj≤d(v10, v7).因d(v10, v7)=d(v7, v10), 所以|d′j-dj|≤d(v7, v10).
由上可知, 当将T(v10)转换至T′(v7)时, 若更改v10的前驱节点为v7, 并将T(v10)-T′(v7)内任意节点i的距离增加d(v7, v10), 即di=di+d(v7, v10), 因di-d′i≤2×d(v7, v10), 因此i的最短距离变化量在后续计算中不超过2×d(v7, v10).此外, 若j的最短距离减少Δ, T(vj)中任意点的最短距离至少减少Δ.
图 2描述了交通网络的一棵最短路径树及异源最短路径树间的差异.图 2a为原始底层交通网络, 共包含1725962个节点, 2864827条边; 在图 2b的最短路径树中, 每个节点(除目的节点A外)都有且仅有一条边连接前驱节点, 故共有1725960条边; 而在图 2c中, 两棵异源(即T(A)和T(B))最短路径树间的差异很小, 仅有1428个节点的前驱节点发生变化.因此, 若仅计算前驱节点发生变化的节点, 则可大幅度降低计算复杂度.
图 2(Fig. 2)
 | 图 2 交通网络下的异源最短路径树Fig.2 Shortest path tree for real transportation network (a)—原始底层网络；(b)—以A为目的节点的最短路径树; (c)—A源和B源最短路径树差异. |
3 重优化算法3.1 异源最短路径树的转换在实现异源最短路径树间的高效转换之前, 需通过Dijsktra等算法求解一棵单源最短路径树T(t1), 再执行以下步骤将T(t1)转换成T(t2).
1) 修改路径P(t2, t1)上所有节点的前驱节点, 即若i∈P(t2, t1), i≠ t1, 令j=pi, 则pj=i;
2) 修改路径P(t1, t2)上所有节点的距离, 即若i∈P(t1, t2), 令Δ=2×(dt2-di), 则di =Δ+ di, 对任意节点k∈T(i), 设置dk =Δ+ dk;
3) 将节点集合V分解成S，T和T1, 初始S={T(t2)}, T=?, T1=V-T-S; 将路径P(t1, t2)上的节点依次插入队列Q′队首;
4) 取出Q′队首节点q, 令T={T(q)}, T1=V-T-S; 将S和T间所有代价差cef < 0的边插入到集合Q中, 其中cef=wef+df-de, (e, f) ∈E, e∈T, f∈S.
5) 从Q中选择代价差最小的边(u, v), 并从Q中剔除(u, v), 其中cef < 0, 设置pu=v, S=S∪T(u), T=T-T(u), 对任意i∈T(u), di=di+cuv;
6) 将T(u)与T间所有代价差cef < 0的边插入Q中, 即(e, f)∈E, e∈T, f∈T(u)；
7) 重复步骤5) 和步骤6), 直至Q为空；
8) S=S+T, 若Q′非空, 则转至步骤4), 否则结束.
3.2 RASP算法RASP算法利用上述转换方法, 从已知最短路径树开始, 依次求解网络所有节点的最短路径树, 从而获得全源最短路径.主要包括以下步骤:
1) 初始化所有节点为未访问节点, 随机选择节点t1作为目的节点, 令t=t1, 利用Dijsktra算法求解单源最短路径及T(t), 标记t为已访问节点;
2) 使用搜索算法(如广度优先搜索算法)从根节点开始搜索下一个未访问节点t′, 利用异源最短路径树转换方法将T(t)转换成T(t′), 标记t′为已访问节点, 并令t= t′;
3) 重复步骤2) 至所有节点都为已访问节点.
由第2节分析可知, t与t′间的最短距离直接影响异源最短路径树的转换效率, 即距离越近, 效率越高, 因此RASP算法优先选择距离t较近的未访问节点t′; 此外, 集合T+T1包含的节点越少, 则搜索空间越小, 转换效率越高, 故RASP算法优先选择具有较少子孙节点的t′.
4 分析4.1 正确性由Dijsktra算法计算得到的初始单源最短路径树是精确解, 故本文只需验证异源最短路径树转换方法的正确性即可确保RASP算法的正确性.证明如下:
1) 在T(t1)转换成T(t2)之前, 在网络中添加虚拟节点t1及虚拟边(t2, t0), 其中w(t2, t0)=d(t2, t1).当更新路径P(t2, t1)和距离, 即完成步骤1) 和步骤2) 后, 任意节点都存在唯一路径至t0, 且其当前记录距离即为该路径长度.后续步骤的目的是调整所有节点的当前路径为到达t0的最短路径.
2) 步骤3) 将节点集合V分解成S, T和T1三部分.其中S为已获得最短路径的节点集合, T为待优化的节点集合, 而T1则是未优化的节点集合.初始时, S={T(t2)}, 第2节已证明S的结构不会发生变化, 即S内所有节点的当前路径即为最短路径; 在步骤5)~步骤7) 中, 若T能将其内节点的路径优化成最短路径, 则S=S+T内的节点都已获得最优解; 经过步骤4)~步骤8) 后, S=V.以下证明集合T内的节点执行步骤5)~步骤7) 后获得最短路径.
3) 在当前生成树中, 边(u, v)的代价差cuv=|P(v, t0)|+w(u, v)-|P(u, t0)|, cuv < 0表示路径P(u, v)+P(v, t0)比当前路径P(u, t0)更短, 需调整以获得更短路径.若网络中所有边的代价差都为非负值, 则所有节点都已获得最短路径.对于边(u, v), u∈T, 在转换之前满足cuv=dv+wuv-du≥0.在最短路径树转换过程时执行步骤1) 和步骤2), 则du=du+Δ1, dv=dv+Δ2.若v∈T, 则Δ1=Δ2, cuv≥0;若v∈T1, 则Δ1 < Δ2, cuv≥0;若v∈S, 则Δ1 > Δ2, cuv可能小于零.因此, 若cuv < 0, 则必有v∈S.令Δ3=cuv < 0为最小的代价差, 则对于任意边(i, j)(u∈T(u), j∈S)的代价差cij=cij-Δ3 > 0, 故T(u)中不存在代价差为负值的边, 且其上所有点的最短距离都减少|Δ3|; 在后续计算中, 集合T-T(u)中的节点距离减少量|Δ4| < |Δ3|, 故也不存在cij < 0的边(i, j)(i∈T(u), j∈T-T(u)).综上, 执行步骤5)~步骤7) 后, S=S+T, T=?, S内部不存在代价差为负值的边, 即集合T经过步骤5)~步骤7) 后所有节点都获得最短路径.
4.2 时间复杂度异源最短路径树转换方法主要经历以下过程:1) 更改路径P(t2, t1)上节点的前驱节点和距离(步骤1) 和步骤2)), 遍历整条路径, 其时间复杂度为O(n1)，其中n1为P(t2, t1)的长度; 2) 步骤4)~步骤7) 首先搜索S与T间所有的边, 并计算其代价差, 其时间复杂度为O(m1), 其中m1为S与T相连边的数量; 然后步骤6) 搜索T(v)与T间所有的边, 时间复杂度为O(m2), 其中m2为S与T(u)相连边的数量, 因T(u)的总量为T, 故O(∑m2)=O(m1); 3) 在步骤3)~步骤8) 中, T的目的是将集合V-S转移到S, 即∑T=V-S.因此, 异源最短路径树转换方法的时间复杂度为O(n1+2×∑ m1)≤O(n+2m).
RASP算法首先执行一次Dijkstra算法以获得初始最短路径树, 其时间复杂度为O(n2); 然后共执行n次异源最短路径树转换方法得到全源最短路径, 其中利用广度(或深度)优先搜索获得下一目的节点, 因此, 异源最短路径树转换的时间复杂度为O(n×(n+(n+2m)))=O(2(n2+nm)).综上所述, RASP算法的时间复杂度为O(n2+2(n2+nm))=O(3n2+2nm).
5 实验与分析为测试RASP算法的正确性和时间效率, 本实验基于Window 7操作系统, 采用Visual C++编程, 在CPU为Intel(R) Xeon(R) E5-265 @2.00GHz, 内存为48GB的图形工作站上, 分别利用现实交通网络和人造网络对本算法进行测试, 并与以下4种算法进行对比.① n-Dijkstra-priority(NDP)算法:Dijkstra算法[10]是经典的求解单源最短路径算法, 根据采用的数据结构不同, 可有多种实现方式, NDP算法采用优先队列, 并执行n次以获得全源最短路径; ② n-Dijkstra-binary(NDB)算法[14]:不同于NDP算法, NDB算法采用二叉树结构, 并使用二分排序法对候选节点进行排序, 每次迭代中选择标记最小的节点; ③ Floyd算法:Floyd算法[9]是经典的求解全源最短路径算法, 在稠密网络中能取得较好的计算效率; ④ improved-Floyd(Ⅰ-Floyd)算法:改进的Floyd算法在时间效率上具有一定的优势.
在测试实验中, 本文RASP算法获得网络中任意点对间的最短距离, 与4种对比算法计算所得的最短路径值相同, 验证RASP算法的正确性.在时间效率方面, 测试结果如下.
5.1 交通网络测试数据集为全国道路网, 共含多个级别的道路, 根据包含道路级别数的不同, 将道路网分成5个大小不同的测试网络:① 网络1包含689155个节点, 1160466条边; ② 网络2包含411719个节点, 946974条边; ③ 网络3包含268326个节点, 349008条边; ④ 网络4包含115122个节点, 149360条边; ⑤ 网络5包含5983个节点, 7468条边.此处定义平均度为边与点的数量之比.表 1为最短路径算法的时间效率对比.
表 1(Table 1)
 表 1 最短路径算法时间效率对比Table 1 Time performance comparison of shortest path algorithms
| 表 1 最短路径算法时间效率对比 Table 1 Time performance comparison of shortest path algorithms | ||||||||||||||||||||||||||||||||||||||||||
对比表 1(其中“×”表示超出内存, 无法获得计算时间; “-”表示计算时间过长)中5种算法的测试结果, 可得出以下结论:
1) RASP算法的运行时间仅为NDP的32%~65%, 为NDB算法的12%左右.其原因在于RASP算法仅搜索最短路径可能发生变化的节点, 即集合T+T1, 故相比于NDP和NDB算法, 大大减少了搜索空间, 提升了计算速度.可见RASP算法在大规模交通网络上, 具有一定的时间优势.
2) 与Floyd和Ⅰ-Floyd算法相比, RASP, NDP和NDB算法在空间复杂度上具有绝对优势, 因为RASP, NDP和NDB算法使用邻接链表(空间复杂度为O(n+m)), 而Floyd和Ⅰ-Floyd算法使用邻接矩阵(空间复杂度为O(n2)), 由于网络1~网络4的数据量较大, Floyd和Ⅰ-Floyd算法无法申请到足够的连续内存, 导致其无法运行.在时间效率上, RASP，NDP和NDB算法也优于Floyd和Ⅰ-Floyd算法.本例测试的交通网络是稀疏网络(平均度为1.7), Floyd和Ⅰ-Floyd算法效率低下.
综上所述, 在交通网络上, RASP算法无论是时间复杂度还是空间复杂度都优于Floyd和Ⅰ-Floyd算法.对比于NDP和NDB算法, RASP算法的运行速度是其运行时间的1.5倍之余.
5.2 人工网络为进一步测试网络特征对算法的影响, 本实验采用由the first DIMACS workshop[15]提供的netgen网络生成器, 构建节点数为10000, 平均度分别为8, 16, 32, 64, 128和256的虚拟网络.
由图 3测试结果可知:① Floyd算法受网络平均度的影响很小, 运行时间保持在1750s左右; RASP算法的计算时间随着平均度的增加而呈现递增的趋势, 但总体效率明显优于Floyd算法; ② NDP算法随着平均度的增加, 其运行时间增长速度比RASP算法快, 效率不如RASP算法; ③ NDB和Ⅰ-Floyd算法在本例测试中, 不具备效率优势; ④ RASP算法较其他所有对比算法始终保持最佳的时间效率.
图 3(Fig. 3)
 | 图 3 算法在不同平均度网络中的时间效率对比Fig.3 Time performance comparison in networks with varying degree |
由此可见, 无论是稀疏网络还是稠密网络, RASP算法的时间效率都具有明显的优势.
6 结论本文基于重优化理论实现了异源最短路径树间的高效转换, 并在此基础上提出了一种适用于大规模网络的全源精确最短路径求解方法——RASP算法.理论证明该算法的时间复杂度为O(3n2+2nm).实验结果表明:在稀疏的交通网络上, RASP算法的运行时间约为NDP算法的32%~65%, 为NDB算法的12%左右, 明显优于Floyd和Ⅰ-Floyd算法; 在平均度变化的人造网络上, RASP算法的运行效率高于NDP, NDB, Floyd和Ⅰ-Floyd算法.因n < m < n2, RASP算法不仅理论时间复杂度在稀疏网络上低, 而且在实际测试中, RASP算法无论是在稀疏还是稠密网络上, 都能取得较好的时间效率, 为快速求解大规模网络的全源最短路径提供了新方法.
参考文献
| [1] | Parichart P, Dongjoo P, Laurence R R, et al. Dynamic and stochastic shortest path in transportation networks with two components of travel time uncertainty[J].Transportation Research Part C:Emerging Technologies, 2003, 11(5): 331–354.DOI:10.1016/S0968-090X(03)00029-9 |
| [2] | 徐业昌, 李树祥, 朱建民, 等. 基于地理信息系统的最短路径搜索算法[J].中国图象图形学报, 1998, 3(1): 39–43. ( Xu Ye-chang, Li Shu-xiang, Zhu Jian-min, et al. A improved best-first search algorithm based on geographical information system[J].Journal of Image and Graphics, 1998, 3(1): 39–43.) |
| [3] | 严寒冰, 刘迎春. 基于GIS的城市道路网最短路径算法探讨[J].计算机学报, 2000, 23(2): 210–215. ( Yan Han-bing, Liu Ying-chun. A new algorithm for finding shortcut in a city's road net based on GIS technology[J].Chinese Journal of Computers, 2000, 23(2): 210–215.) |
| [4] | 吴京, 景宁, 陈宏盛. 最佳路径的层次编码及查询算法[J].计算机学报, 2000, 23(2): 184–189. ( Wu Jing, Jing Ning, Chen Hong-sheng. Hierarchical encoding of optimal path and its retrieval[J].Chinese Journal of Computers, 2000, 23(2): 184–189.) |
| [5] | Ahmed Y H. A genetic algorithm for finding the k shortest paths in a network[J].Egyptian Informatics Journal, 2010, 11(2): 75–79.DOI:10.1016/j.eij.2010.10.004 |
| [6] | Cherkassky B V, Goldberg A V, Radzikt T. Shortest paths algorithms:theory and experimental evaluation[J].Mathematical Programming, 1996, 73: 129–174. |
| [7] | 陆锋. 最短路径算法:分类体系与研究进展[J].测绘学报, 2001, 30(3): 269–275. ( Lu Feng. Shortest path algorithms:taxonomy and advance in research[J].Acta Geodaetica et Cartographica Sinica, 2001, 30(3): 269–275.) |
| [8] | 李鸣鹏, 邹兆年, 高宏, 等. 不确定图上期望最短距离的计算[J].计算机研究与发展, 2012, 49(10): 2208–2220. ( Li Ming-peng, Zou Zhao-nian, Gao Hong, et al. Computing expected shortest distance in uncertain graphs[J].Journal of Computer Research and Development, 2012, 49(10): 2208–2220.) |
| [9] | Floyd R W. Algorithm 97:shortest path[J].Communications of ACM, 1962, 5(6): 345. |
| [10] | Dijkstra E W. A note on two problems in connection with graphs[J].Numerische Mathematik, 1959, 1(1): 269–271.DOI:10.1007/BF01386390 |
| [11] | 刑星星, 赵国兴, 骆祖莹, 等. 基于GPU的全源最短路径算法[J].计算机科学, 2012, 39(3): 299–303. ( Xing Xing-xing, Zhao Guo-xing, Luo Zu-ying, et al. GPU-based algorithm of shortest path[J].Computer Science, 2012, 39(3): 299–303.) |
| [12] | Miller-Hooks E, Yang B. Updating paths in time-varying networks given arc weight changes[J].Transportation Science, 2005, 39(4): 451–464.DOI:10.1287/trsc.1040.0112 |
| [13] | Pallottino S, Scutelli M.Shortest path algorithms in transportation models:classical and innovative aspects[C]// Marcotte P, Nguyen S.Equilibrium and Advanced Transportation Modeling.Boston:Kluwer Academic Publishers, 1998:245-281. |
| [14] | Xu M H, Liu Y Q, Huang Q L, et al. An improved Dijkstra's shortest path algorithm for sparse network[J].Applied Mathematics and Computation, 2007, 185(1): 247–254.DOI:10.1016/j.amc.2006.06.094 |
| [15] | Johnson D S, McGeoch C C. Network flows and matching:first DIMACS implementation challenge[M]. Provindence: American Mathematical Society, 1993. |
