２Ｏ１７年笫４ 总； １８５ 基于并行计算的大规模图多源最短路径算法设计 万一红徐常福 （江西财经大学软件与通信 程学院，江西南昌３３００３２） 摘要：大数据时代的到来，社交网络、交通网络等抽象的图结构的规模也越来越大，面对数据量大、结构复杂的 图数据的最短路径计算，原始的最短路径算法已经不再适用，数据的并行化处理是大规模图计算较为常用的方 法。在实际应用中往往需要计算任意两点问的最短路径，因此多源最短路径算法的研究是有意义的。本文参考 Ｆｌｏｙｄ算法思想，提出一个并行处理的大规模图多源最短路径算法，该算法将图中节点与边的关系抽象为矩阵， 再通过矩阵分割的方式，将超大规模的矩阵切分为多个子矩阵进行并行处理，减少最短路径计算中算法迭代时 间复杂度以提高算法的执行效率。 关键词：多源最短路径；并行计算；矩阵分割 中图分类号：ＴＰ３０１ 文献标识码：Ａ 文章编号：１６７１—４７９２（２０１７）４．００６８ ０５ Ａｌｌ－ｐａｉｒ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｐａｒａｌｌｅｌ Ｃｏｍｐｕｔｉｎｇ Ｗａｎ Ｙｉｈｏｎｇ Ｘｕ Ｃｈａｎｇｆｕ （Ｓｃｈｏｏｌ ｏｆＳｏｆｔｗａｒｅ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＦｉｎａｎｃｅ ａｎｄ Ｅｃｏｎｏｍｉｃｓ， Ｊｉａｎｇｘｉ Ｎａｎｃｈａｎｇ ３３００３２） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｅ ｅｒａ ｏｆ ｂｉｇ ｄａｔａ，ｇｒａｐｈ ｓｔｒｕｃｔｕｒｅｓ ｓｕｃｈ ａｓ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ａｎｄ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｎｅｔｗｏｒｋ ａｒｅ ｂｅｃｏｍｉｎｇ ｉｎ－ ｃｒｅａｓｉｎｇｌｙ ｌａｒｇｅ．Ａｔ ｐｒｅｓｅｎｔ，ｇｒａｐｈ ｄａｔａ ａｒｅ ｉｎ ｇｒｅａｔ ａｍｏｕｎｔ ａｎｄ ｏｒｉｇｉｎａｌ ｓｈｏｒｔｅｓｔ ｐａｔｈ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｎｏ ｌｏｎｇｅｒ ａｐｐｒｏ— ｐｒｉａｔｅ．Ｐａｒａｌｌｅｌ ｐｒｏｃｅｓｓｉｎｇ ｉｓ ａ ｃｏｍｍｏｎ ｍｅｔｈｏｄ ｆｏｒ ｌａｒｇｅ—ｓｃａｌｅ ｇｒａｐｈ ｃａｌｃｕｌａｔｉｏｎ．Ｉｎ ａｃｔｕａｌ ａｐｐｌｉｃａｔｉｏｎ，ｗｅ ｎｅｅｄ ｔｏ ｃｏｍｐｕｔｅ ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｂｅｔｗｅｅｎ ａｎｙ ｔｗｏ ｐｏｉｎｔｓ，ａｎｄ，ｔｈｅｒｅｆｏｒｅ，ｔｈｅ ｓｔｕｄｙ ｏｆ ｍｕｌｔｉ－ＳＯＵｌ￣Ｃｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ａｌｇｏｒｉｔｈｍ ｍａｋｅｓ ｓｅｎｓｅ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｒｅｆｅｒｒｉｎｇ ｔｏ ｔｈｅ ｍａｉｎ ｉｄｅａ ｏｆ Ｆｌｏｙｄ ａｌｇｏｒｉｔｈｍ，ｗｅ ｐｒｅｓｅｎｔ ａ ｐａｒａｌｌｅｌ ｍｕｌｔｉ—ｓｏｕｒｃｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｌａｒｇｅ・ｓｃａｌｅ ｇｒａｐｈ．Ｔｈｉｓ ｃａｌｃｕｌａｔｉｏｎ ａｂｓｔｒａｃｔｓ ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｎｏｄｅｓ ａｎｄ ｅｄｇｅｓ ｉｎ ｔｈｅ ｇｒａｐｈ ａｓ ａ ｍａｔｒｉｘ，ｄｉｖｉｄｅｓ ｔｈｅ ｌａｒｇｅ ｍａｔｒｉｘ ｉｎｔｏ ｓｅｖｅｒａｌ ｓｕｂ－ｍａｔｒｉｃｅｓ ａｎｄ ｐｒｏｃｅｓｓｅｓ ｔｈｅｍ ｉｎ ｐａｒａｌｌｅ１．Ｉｔ ｃａｎ ｒｅｄｕｃｅ ｔｈｅ ｉｔｅｒａ— ｔｉｏｎ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ，ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｅｆｉｃｉｆｅｎｃｙ ｏｆｔｈｅ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：Ｍｕｌｔｉ－ｓｏｕｒｃｅ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ；Ｐａｒａｌｌｅｌ Ｃｏｍｐｕｔｉｎｇ；Ｍａｔｒｉｘ Ｐａｒｔｉｔｉｏｎ ０引言 等。 最短路径问题是图论中比较经典的问题。随着 最基础的最短路径是研究单源最短路径，也就 是研究网络中从某个源节点到所有节点的最短路 径。单源最短路径算法中Ｄｉｊｋｓｔｒａ算法【６Ｊ是比较经典 现代科技的迅速发展，最短路径的应用场景多种多 样，应用十分广泛。近年来比较热门的交通网络、汽 车导航的最短路径【Ｉ－３】，以及社会网络分析的运用 、 路由算法的研究［５】等。最短路径的研究是为了求解许 多问题的最高效率问题，它不仅仅是字面意义上的 路径最短，还可以是时间最少、开销最少、性能最优 一的，对于计算一个带权图，该算法可以在０（（Ｍ＋Ｎ） ｌｏｇ＿Ｎ）时间完成一个节点到其他所有节点的最短路 径的计算。近期，许多学者在对单源最短路径的求解 上有了新的改进，文献ｆ７ １１］提出了在不同数据集下 ６８一 的单源最短路径计算算法。然而只求得单源最短路 径不能满足需求，求多源最短路径的算法应运而生。 Ｆｌｏｙｄ算法是比较经典的多源最短路径算法，它被 大量用在解决所有节点的最短路径问题。Ｆｌｏｙｄｔ 用 ｊ ｎ｝。 定义２将路径的权值集合ｗ用ｎ×ｎ的矩阵 表示，即： ２ 三个嵌套循环遍历这些节点来计算所有节点中的最 优路径，这很容易使用程序循环来实现。另一种求 解多源最短路径的方法是重复使用单源最短路径算 法。源节点顺序得沿着节点列表来变化，并行计算当 Ｗ＝ Ｗ２２ ●●● ●●● 前源节点的单源最短路径。这种方法可以很好的实 现并行化计算，每一个源节点路径的计算都可以通 过一个或多个处理器来执行，它的算法时间复杂度 与Ｆｌｏｙｄ算法相似，但是它与Ｆｌｏｙｄ算法的最大差 别是，Ｆｌｏｙｄ算法适合于节点密集的网络中，重复使 用单源最短路径算法适合于稀疏的网络节点中，例 如交通运输网络。 大数据时代的到来，网络中的数据庞大且类型 复杂，使原有的传统最短路径算法不再适用。对于 ，，，Ｊ．．．．．．．．．．．。。，，．，．．．．．。。。．．．．． 大规模图的处理，近几年用的最多的方法是并行化 ～ 处理，将大规模图切分成多个子图并交给多个处理 节点并行计算，以加快算法的求解速度。目前大规 ● ● ● ● ● ● ● ● 模图最短路径求解的算法有许多不足，首先，对大规 模图的多源最短路径算法的研究文献较少，．～ 但实际 应用中很多情况需要求解图的多源最短路径。其次， 图计算中算法执行效率受算法的迭代次数影响，过 多的迭代计算不仅降低了算法的执行效率，而且迭 代过程中产生的中间结果保留在内存中占用了宝贵 的内存资源。根据这两点，本文提出一个减少算法 迭代次数的大规模图并行多源最短路径算法。 １任务模型 在详细描述本算法前，先对以下几个概念进行 定义。 定义１带权有向图Ｇ＝（Ｖ，Ｅ，Ｗ），其中Ｖ表示 节点集，Ｖ＝｛ｖ ，Ｖ２，…，Ｖｎ｝，Ｅ表示路径集，Ｅ＝｛ｖｉｖｊ［ｉ＃ ｊ，ｌｓ ｉ，ｊ ｎ），、，ｉｖｊ表示有序节点＜ｖ ，ｖ＿ｉ＞相关联的路 径，ｗ表示每条路径的权值集合，Ｗ＝｛ｗｉｊｌｉ＃Ｊ，ｌ ｉ， 用矩阵可以表示任意两点间的路径的权值，并 且通过矩阵变换，可以求得任意两点问的最短路径 的权值。 路径的权值矩阵ｗ的第ｉ行的元素都是由节 点Ｖｉ出发。如果 和ｖｉ之间有相连的路径，则给第ｉ 行第Ｊ列的元素ｗ 赋值，且Ｗｉｉ的大小为ｖｉ到Ｖ＿ｉ的 路径的和。路径的权值矩阵的定义形式为：对角线的 值为０，表示节点ｖｉ到节点ｖｉ的路径为０；ｗ ｉ的值无 穷大，表示节点 到节点ｖｊ没有路径相连；ｗ ∈（０， ＋ｏ。），表示节点 到节点ｖｊ有路径相连，且路径的 权值为ｗ日，表示如下： ｌ０ ，ｉ＝ ，＝｛ｏＯ ， 与ｖ，不可达 （２） ｌ其他，ｖ，－￣ｖ 有路径 定义３权值矩阵ｗ以＜Ｖｉ，ｖｊ，ｗｉｉ＞三元组的形 式存储在一个文本文件中，ｗｉｉ＝０不记录。 定义４最短路径是ｖｉ到ｖｊ的各通路中路径的 权值的和为最小的通路。 定义５路径的权值矩阵ｗ的第ｉ行的元素都 是由节点ｖ 出发，定义ｍｘ ｎ维矩阵可计算范围内 的节点集合Ｖ—ｆｖ １０＜ｉ￣ｎ｝。 ２最短路径并行计算 前文我们将节点以图结构的形式表示，并完成 了对最短路径的权值矩阵的描述。接下来我们要运 用最短路径并行算法，求得任意节点间的最短路径。 ２．１算法思想 本算法计算大规模图的多源最短路径，图数据 以矩阵的形式存储，在Ｆｌｏｙｄ算法动态规划的思想 一６９一 上，对矩阵进行先切分再连接的并行计算。 是按行切分矩阵的方法，将原矩阵切分为ｋ个Ｉｘ ｎ 本算法将节点路径图用带权有向图Ｇ＝｛Ｖ，Ｅ， ｗ｝表示，节点路径的权值用ｎ×ｎ维的矩阵ｗ表示。 维的子矩阵。其中厂ｌ０ ］：ｌｌ 孚ｌ‘ Ｉ。 算法的步骤如下： 第二点，矩阵分割后丢失的信息。南于路径的权 第一步，矩阵分割，将矩阵ｗ按行平均分割成 值矩阵ｗ的第ｉ行的元素都是由节点ｖｉ出发，所以分 ｋ个ｌｘ ｎ维的子矩阵。 割后的子矩阵只保留了由节点ｖ 到ｖ，＋ 出发的路径。 第二步，子矩阵多源最短路径计算，运用多台计 第ｊ点，矩阵分割后的优点。这是一种“分而治 算机并行计算子矩阵可计算范同内的任意节点的最 之”的方式，将大型的矩阵分割为若干个子矩阵，就 短路径，得到部分节点的最短路径的权值矩阵。 可以使用多台计算机同时计算这些子矩阵，因此在 第■步，迭代求解最优路径。将子矩阵两两合 子矩阵中最短路径的迭代计算可以并行执行。 并，得到新的子矩阵，再对新的子矩阵做计算，此处 矩阵分割的具体方法如下： 的子矩阵计算不同于第二步，权值矩阵中只有部分 设路径的权值矩阵为： 数据需要更新，得到新的部分节点的最短路径的权 值矩阵，第一步这个过程称为一次迭代计算。 第四步，重复第ｊ步的过程，直到迭代计算完 ：Ｉ ｔ 成。迭代计算完成的标志是子矩阵迭代计算的次数 Ｉｌ… 达到算法的预设值。算法基本流程如图一所示。 ｆ 。 将矩阵ｗ按行分割为大小相同的ｋ个子矩阵。 将ｗ按行分割，使得Ｗ＝｛Ｗ ，Ｗ２，…，ＷｋｌＩ（＝ ～ ｌ■Ｉ广 １ ＝２ ｝，ｋ表示切分的子矩阵个数，ｌ表示子矩阵行 数， 为ｌｘ ｎ阶矩阵。ｗ切分后的子矩阵为： ｆ 跃（ —１）｝ｌ Ｗ｛ｆ 一１））２ Ｗ｛』ｘ（ｉ—ｌ Ｉ ．１）＋１）１ Ｗ｛ｔｘｏ－ｍｌ｝２ ，×（ １）＋ｌ （３） ：ｗ｛Ｊ 一１）＋Ｊ｝１ ｗ｛ｆ×（ｊ。）＋ｊ）２ ｗ｛Ｊ￣￣ｉ－１）＋伽 是 Ｗｉ＝｛ｗｒ￣ｌＰ＃ｑｌｌｘ（ｉ一１）≤ｐ≤ｌｘ（ｉ～１）十ｌ，１ｓ ｑ≤ｎ｝，１≤ｉ ｋ 图一算法摹本流程 ２．２矩阵分割 矩阵分割的过程中，我们需要讨论三点：第一 则 ：● 点，矩阵的分割方式；第二点，分割后的子矩阵相比 原矩阵会丢失哪些信息；第三点，矩阵分割的优点。 第一点，矩阵的分割方式。在本算法中，使用的 ｗ 表示在子矩阵Ｗｉ中，从节点Ｖｐ到节点Ｖｑ最 一７０一 多经过ｍ个节点的最短路径，０≤ｍ≤ｎ一２。切分后 矩阵ｗｉ经过矩阵路径计算后，最初的Ｗｉ的值 被覆盖，得到的新矩阵Ｗ。描述的就是局部节点的 的路径集合为： Ｅｉ＝｛ｗｐｑＩｐ≠ｑｌ，Ｉｘ（ｉ一１）≤ｐ≤≤ｌｘ（ｉ—１）＋ｌ， １≤ｑ－＜ｎ｝ （４） 最短路径，ｗｉ就是本节要求的局部节点的最短路径 的权值矩阵。 ２．４迭代求解最优路径 设定两个参数，参数ｃｏｕｎｔ记录迭代的次数，子 矩阵合并，并且求解合并后子矩阵的路径称为一次 分割后的子矩阵将交给不同的计算机进行下一 步的计算，子矩阵间的计算是并行执行的。 ２．３并行局部路径求解 局部路径的求解就是要找到局部节点的最短路 迭代，参数是预计的合并次数，给ｃｏｕｎｔ赋初始值， 径的权值矩阵，局部最短路径的求解有两种计算模 型，即首次子矩阵路径最短计算模型与合并后的子 矩阵最短路径计算模型。 首次子矩阵路径最短计算方法与Ｆｌｏｙｄ算法类 似，针对某个子矩阵 ，在矩阵Ｗｉ可计算范围内的 节点，如果Ｏ＜ｗｐｑ，、Ⅳｍ＜ ，矩阵可计算范围内的节 点，说明有一条路径是由节点Ｖｐ经过节点ｖ 到达节 点 的，并且这个距离值为、 ＝、；ｌ，ｐ ＋ 。因为要求的 是Ｖｐ经过节点ｖｑ到达节点 的最短距离，所以要 针对所有的０＜ｔｓ ｎ，Ｉｘ（ｉ一１） ｐ＜ｌ×（ｉ一１）＋１迭 代计算求出 ，找到它的最小值，这个过程称为矩 阵路径计算。Ｗ试的计算公式如下： Ｉｘ（ｉ－１）＋１ ．ｗ １）（ ， ＋Ｗｑｆ） ‘５’ 当ｗ ｗ ＿ｗ 时，要将路径ｖｐ、ｒｑＶｔ添加到路径 集合Ｅ．中，记录经过了ｖＩ的最短路径。 两两合并后的子矩阵最短路径计算，有一部分 数据是不需要更改的，例如１＝２，子矩阵ｗ，与子矩 阵ｗ２合并后得到的新矩阵ｗ 中，如式（６）所示， 方框内的值是已经计算完成的，合并后的子矩阵计 算不需要再对它们进行修改。 ｗｌ３ ｗ２３ ２＝ （６） ｗ３３ ｗ３４ ｗ４３ Ｗ４４ Ｌ， 即ｃｏｕｎｔ＝０。每开始一次迭代ｃｏｕｎｔ自加１，当 ｃｏｕｎｔ＝Ｔ时迭代计算结束。 首先将子矩阵进行第一次两两合并，得到新的 子矩阵，ｃｏｕｎｔ自加ｌ，即ｃｏｕｎｔ－－Ｏ，表示是矩阵的第 一次迭代。矩阵第一次合并后，子矩阵的行数为： Ｉ（。。 ．Ｄ）＝２。 ×ｌ（。∞ ｏ） （７） 合并后的子矩阵ｗｉ一是一个｛ｌ 。 ×（ｉ一１） ＋ｌ 咄ｏ１）ｘ ｎ维矩阵，矩阵的下标ｉ表示合并后的矩 阵位数，上标ｃｏｕｎｔ表示是第ｃｏｕｎｔ次合并后得到的 子矩阵。 合并后的子矩阵为： 酬删｝・ 删ｘ（ｆ＿Ｉ】｝２ ＝ ｗ｛｛ １ 一Ｉ）＋ｌ １ １）＋８２ 一 ＋ ）１ 叫（州一９｝２ ｌ删）（（¨） 一 ）＋Ｉ （８） ・・ Ｗｒ托— ） （Ｈ ＝Ｉ） 、 Ｗｊ ＝Ｗｆ＋ Ｗ。＋１：｛ｐ≠ｑＩ １ ｎ：ｏ）×（ｉ一１） ｐ－ｌ（。 １ ０） ×（ｉ一１）＋ｌ 。 Ｄ），１ｓ ｑ≤１１｝，此时子矩阵的个数为 ｋ＝２ 个。为了方便之后的迭代计算，完成一次合 后，重新定义矩阵维矩阵｛ｌ（ｃ帆毗。）×（ｉ一１）＋ｌ 。）｝× ｎ，令Ｗｉ＝ｗ 。 然后，针对合并后的子矩阵Ｗ计算ｗｐ，ｔ。计算 一７１～ 方法为上一节的矩阵局部路径求解。每完成一次迭 代，比较ｃｏｕｎｔ值。 似算法［Ｊ】．软件学报，２０１１，（１Ｏ）． 【５】刘莉莉，徐野，无标度的ＷＳＮｓ路由算法研究【Ｊ］．沈阳 理工大学学报，２０１６，（０６）． 若ｃｏｕｎｔ￣Ｔ，则迭代求解最优路径完成，Ｗｉ描 述的就是任意节点间的最短路径，ｗｉ是ｖｐ到Ｖｑ的 任意两点间的最短路径的权值矩阵，ｐ≠ｑ，１≤ｐ， ｎ。 若ｃｏｕｎｔ＞Ｔ，则进入下一次迭代求解。 ３结束语 图的最短路径计算为网络分析提供了重要的参 考数据，将大规模的图并行化处理，使用多台计算机 同时计算，加快了最短路径算法的执行。将图以文 本的形式存储，以矩阵的逻辑计算可以解决矩阵对 于大规模稀疏图存储占用过多的存储空间的问题， 运用矩阵的逻辑运算，引用Ｆｌｏｙｄ算法的思想，将矩 阵切分并行化计算，将子矩阵中的最短路径的迭代 并行实现，减少了迭代计算的时问，加快了多源最短 路径算法的执行效率。 参考文献 【１］Ｃｈｕｎ Ｊｉａｎｇ Ｚｈｕａ，Ｋａｍ－Ｙｉｕ Ｌａｍａ，Ｓｏｎｇ Ｈａｎｂ．Ａｐｐｒｏｘｉ・ ｍａｔｅ ｐａｔｈ ｓｅａｒｃｈｉｎｇ ｆｏｒ ｓｕｐｐｏｒｔｉｎｇ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｑｕｅｒｉｅｓ ｏｎ ｒｏａｄｎｅｔｗｏｒｋｓ．００２０—０２５５／？２０１５Ｅｌｓｅｖｉｅｒｌｎｃ．Ａｌｌｒｉｇｈｔｓｒｅｓｅｒｖｅｄ． 【２１Ｇ．Ｋｅｌｌａｒｉｓ，Ｋ．Ｍｏｕｍｔｉｄｉｓ，Ｓｈｏｒｔｅ￣ｐａｔｈ ｃｏｍｐｕｔａｔｉｏｎ ｏｎ ａｉｒ ｉｎｄｅｘｅｓ，ＰＶＬＤＢ３（１）（２０１０）７４７－７５７． 【３】卢照，师军。于海蛟，等．城市路网的最短路径并行求 解【Ｊ】．计算机技术 发展，２０１０，（０１）． 【４】唐晋韬，王挺，王戟．适合复杂网络分析的最短路径近 一７２一 ［６］Ｄｉｊｋｓｔｒａ，Ｅ．Ｗ．Ａ ｎｏｔｅ ｏｎ ｔｗｏ ｐｒｏｂｌｅｍｓ ｉｎ ｃｏｎｎｅｘｉｏｎ ｗｉｔｈ ｇｒａｐｈｓ［Ｊ１．Ｎｕｍｅｒｉｓｃｈｅ Ｍａｔｈｅｍａｔｉｋ，１９５９，（Ｏ１）：２６９—２７ｌ， 【７］Ｃｈｕｎ Ｊｉａｎｇ Ｚｈｕａ，Ｋａｍ—ＹｉｕＬａｍａ，ＳｏｎｇＨａｎｂ．Ａｐｐｒｏｘｉ— ｍａｔｅ ｐａｔｈ ｓｅａｒｃｈｉｎｇｆｏｒ ｓｕｐｐｏｒｔｉｎｇ ｓｈｏｒｔｅ￣ｐａｔｈｑｕｅｒｉｅｓ ｏｎ ｒｏａｄ ｎｅｔｗｏｒｋｓ．００２０—０２５５￣０１ ５ Ｅｌｓｅｖｉｅｒ ｌｎｅ．Ａｌｌ ｒｉｇｈｔｓ ｒｅｓｅｒｖｅｄ． 【８］Ｃｈｕｎ Ｊｉａｎｇ Ｚｈｕａ，Ｋａｍ—ＹｉｕＬａｍａ，ＳｏｎｇＨａｎｂ．Ａｐｐｒｏｘｉ— ｍａｔｅ ｐａｔｈ ｓｅａｒｃｈｉｎｇ ｆｏｒ ｓｕｐｐｏｒｔｉｎｇ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｑｕｅｒｉｅｓ ｏｎ ｒｏａｄ ｎｅｔｗｏｒｋｓ．００２０－０２５５￣０１ ５ Ｅｌｓｅｖｉｅｒ Ｉｎｃ．Ｍ１ ｉｒｇｈｔｓ ｒｅｓｅｒｖｅｄ． 【９］Ｃｈｕｎ Ｊｉａｎｇ Ｚｈｕａ，Ｋａｍ－Ｙｉｕ Ｌａｍａ，Ｓｏｎｇ Ｈａｎｂ．Ａｐｐｒｏｘｉ— ｍａｔｅｐａｔｈ ｓｅａｒｃｈｉｎｇｆｏｒ ｓｕｐｐｏｒｔｍｇ ｓｈｏｒｔｅ￣ｐａｔｈ ｑｕｅｒｉｅｓ ｏｎ ｒｏａｄ ｎｅｔｗｏｒｋｓ．００２０－０２５５／２０１５ Ｅｌｓｅｖｉｅｒ ｌｎｃ．Ａｌｌ ｉｒｈｇｔｓ ｒｅｓｅｒｖｅｄ． 【ｌＯ］Ｕ．Ｍｅｙｅｒ，Ｐ．Ｓａｎｄｅｒｓ．Ｄｅｌｔａ－ｓｔｅｐｐｉｎｇ：Ａ ｐａｒａｌｌｅｌｉｚａｂｌｅ ｓｈｏｒｔｅｓｔｐａｔｈａｌｇｏｒｉｔｈｍ［Ｊ］．Ｊ．Ｍｇｏｒｉｔｈｍｓ，２００３，４９（０３）：１１４—１５２． 【ｌ １］ｓ．Ｍａｌｅｋｉｙｚ，Ｄ．Ｎｇｕｙｅｎｘ，Ａ．Ｌｅｎｈａｒｔｈｘ．Ｍ．Ｇａｒｚａｒ￣ｎｙ， Ｄ．Ｐａｄｕａｙ，Ｋ．Ｐｉｎｇａｌｉｘ．ＤＳＭＲ：Ａ Ｐａｒａｌｌｅｌ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｓｉｎ— ｇｌｅ—Ｓｏｕｒｃｅ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｐｒｏｌ￣ｌｅｍ．ＩＣＳ’１６，Ｊｕｎｅ ０１—０３，２０１６， Ｉｓｔａｎｂｕ１．Ｔｕｒｋｅｙｃ ２０１６ ＡＣＭ．ＩＳＢＮ ９７８—１—４５０３—４３６１—９／１６／０６． 【１ ２］Ｆｌｏｙｄ，Ｒｏｂｅｒｔ Ｗ．Ａｌｇｏｒｉｔｈｍ ９７：Ｓｈｏｒｔｅｓｔ Ｐａｔｈ【Ｊ】．Ｃｏｍ— ｍｕｎｉｃｍｉｏｎｓ ｏｆｔｈｅ ＡＣＭ，１９６２，５（０６）． 作者简介 万一红（１９９３一），女，硕上研究生，主要研究方向：大数 据分析； 徐常福（１９９１～），男，硕上研究生，主要研究方向：社交 网络分析、软件工程。