基于带标签路网的高效最短路径索引动态维护方法

摘要

本发明公开了基于带标签路网的高效最短路径索引动态维护方法，其包括以下内容：a)提出一种基础方法维护CHLR索引，找出所有受影响的边，并对收缩得到它们的点重新收缩计算；b)提出一种新的方法维护CHLR索引，只传递发生变化的边上的影响；c)提出一种优化方法维护CHLR索引，借助捷径支持量的概念进一步减少对未发生变化的边进行的不必要计算；d)提出批量维护方法维护CHLR索引，通过给边分配层级数，按层级从高到低依次更新。本发明首次提出在带标签路网上动态维护最短路径索引结构方法。解决了带标签的路网动态发生变化时，如何维护最短路径索引从而提升最短路径查询效率这一实际问题。

说明书

技术领域

本发明属于计算机科学领域，具体涉及基于带标签路网的高效最短路径索引动态维护方法。

背景技术

在图算法中，最短路径问题一直广泛关注，因为它有很多应用价值，随着互联网的迅速普及和应用，导航软件已经成为很多人出门必需的工具，通过导航软件可以获得两点间最短距离的路径、或所需时间最短的路径。当前已经提出了很多查询最短路径的算法，这些算法可以分为无索引的和基于索引的两类，无索引的包括传统的Dijkstra、Bellman、Floyd等。最近也提出了很多基于索引的算法，比如Hub Labeling(HL)通过减少最短路径上的点提升查找效率，基于HL的PLL和PSL。通过引入“捷径”这一概念，ContractionHierarchies(CH)可以减少查询最短路径过程的搜索和迭代，从而加速最短路径查询过程。

从2015年到2020年，手机地图用户数量从6.05亿增长到7.68亿，但是对于现实中很多实际应用场景，只考虑物理意义上的两点之间的最短路径是不够的，还需要考虑道路的实际场景。比如有的司机想避开收费路段即便距离更短，或者对于一些特殊类型的大型货车等需要避开禁行路段。对于这些场景，还需要考虑道路类型，也就是路网的边的类型，所以对于用户数量如此庞大的手机地图应用，查询最短路径的时候，除了寻找最短的物理距离，还应该注意边上的标签信息。基于CH索引，目前也有工作提出了带标签路网上构建最短路径索引的算法ContractionHierarchiesLabelRestrictions(CHLR)。

在现实应用中，路网是在不断变化的，节日期间原本收费的高速公路会不再收费、只在某些时间段大型货车禁行、修路期间会封闭某些道路，此外，道路的实际情况也在不断改变，比如在高峰时间段道路处于拥挤状态。当前也有很多收集实时路况信息的平台，比如某德地图中85％的实时交通数据来自众包，鉴于使用某滴、某德地图等平台用户基数相当庞大，他们可以通过众包的方法几乎全覆盖地提供道路的情况。为了在动态变化过程中，实时提供最短路径结果，人们需要设计动态网络中维护最短路径索引的方法。

根据调研，目前还没有算法给出解决动态维护带标签路网中最短路径索引的方法，本问题的解决具有重要的现实应用价值。

发明内容

本发明的目的是提供动态标签路网中，维护最短路径索引的方法，即给定一个边上带标签的图网络，当边的权重增加或减小、边的标签类型发生变化时，动态更新图上的最短路径索引结构。

实现本发明目的的具体技术方案是：

一种基于带标签路网的高效最短路径索引动态维护方法，该方法包括以下具体步骤：A1：构建好CHLR索引图，当索引图的一条边(q,v)发生变化，根据CHLR索引图给定的优先级，找出边(q,v)端点中优先级更小的点，假定是q；根据构建CHLR索引的方法，如果存在边(u,q)和边(q,v)产生的捷径(u,v)，那么边(q,v)的变化会影响到捷径(u,v)，将点q加入存储所有需要重新收缩的点的集合θ；

A2：捷径(u,v)端点中优先级更小的点加入到集合θ，继续传递本次变化带来的影响；

A3：对集合θ中的点重新进行构建CHLR索引中的收缩操作，得到更新后的CHLR索引图。

又一种基于带标签路网的高效最短路径索引动态维护方法，该方法包括以下具体步骤：B1：构建好CHLR索引图，如果索引图上的一条捷径边e＝(u,v)是由边e′＝(u,q)和e″＝(q,v)收缩而得到的，那么e′和e″是e的父母，e是e′和e″的孩子，e′是e″的伴侣；一条边的变化等价于旧标签下的边权重变为无穷，新标签下的边权重变为新的权重，重新计算新旧标签下的捷径权重，即找出重新计算的边原图的边权重和它所有父母对边权重和的最小值；B2：创建优先队列Q，将发生变化的边根据边的优先级插入优先队列Q，边的优先级比较方法是，边的端点中优先级较小的点进行比较，点的优先级低的对应边的优先级低，如果这个值相等，则标签个数少的边优先级低；

B3：维护发生变化的边的捷径域，对于同一起止点下的两条边e和e′，如果边e的边权小并且标签限制更少，即w(e)≤w(e′)并且

B4：对优先队列Q的边逐一处理，对当前元素e，找出e的所有伴侣和这对父母的孩子，如果e增加，需要重新计算孩子的捷径权重，如果e减小，直接计算是否会产生更短的孩子捷径，对于变化的捷径需要插入优先队列Q并维护变化的捷径的捷径域；处理完优先队列Q中全部边后，得到更新后的CHLR索引图。

另一种基于带标签路网的高效最短路径索引动态维护方法，该方法包括以下具体步骤：C1：构建好CHLR索引图，记录索引图上所有捷径的支持量，即支持当前捷径权重的父母对的数量；如果原图边权重等于捷径权重，支持量加1；

C2：重新计算新、旧标签下对应边的新的权重，将原图上边的长度和这条边所有父母边权和的最小值作为新的权重；创建优先队列Q存储发生变化的边，如果新的边权重减小了，则直接更新，如果边权重增加，则暂不做更新，只插入优先队列Q，记录该边权重增加；维护捷径支持量，如果更新后边权重等于当前对应捷径权重，则支持量加1，如果捷径权重发生了变化，需要重新计算支持量，变化的边插入优先队列Q；

C3：将发生变化的边根据边的优先级插入优先队列Q，边的优先级比较方法是，边的端点中优先级较小的点进行比较，点的优先级低的对应边的优先级低，如果这个值相等，则标签个数少的边优先级低；

C4：维护发生变化的边的捷径域，对于同一起止点下的两条边e和e′，如果边e的边权小并且标签限制更少，即w(e)≤w(e′)并且

C5：对优先队列Q的边逐一处理，对当前元素e，找出e的所有伴侣和这对父母的孩子；当e增加，如果e的原权重刚好是支持当前孩子捷径权重的一种情况，那么该孩子捷径支持量减1，如果孩子捷径支持量小于1，则孩子捷径权重会增加，暂不做更新，插入优先队列Q；当e减小，如果e更新后的权重支持当前捷径权重，则孩子捷径支持量加1，如果当前父母对能产生更短的孩子捷径，则更新孩子捷径；

C6：鉴于只对减小的边进行直接更新，对增加的边暂不做更新，所以对于增加的捷径e，重新计算e的权重，看原来能被e覆盖的边是否不再能被覆盖，而对于e减小，看e是否能覆盖更多的边，根据步骤C2维护捷径的支持量；当优先队列Q为空时，得到更新后的CHLR索引图。

再一种基于带标签路网的高效最短路径索引动态维护方法，该方法包括以下具体步骤：D1：构建好CHLR索引图，记录索引图上所有捷径的支持量，即支持当前捷径权重的父母对的数量；如果原图边权重等于捷径权重，支持量加1；给索引图上的捷径分配层级，如果一条捷径没有孩子那么这条捷径的层级是1，否则这条捷径的层级是所有孩子层级的最大值加1；D2：对于一批要更新的边，按照层级数从高到低进行更新，同一层级的边通过一起更新，对于一条要更新的边，重新计算新、旧标签下对应边的新的权重，将原图上边的长度和这条边所有父母边权和的最小值作为新的权重；如果新的边权重减小了，则直接更新，如果边权重增加，则暂不做更新，只插入优先队列Q，记录该边权重增加；维护捷径支持量，如果更新后边权重等于当前对应捷径权重，则支持量加1，如果捷径权重发生了变化，需要重新计算支持量，变化的边插入优先队列Q；

D3：将发生变化的边根据边的优先级插入优先队列Q，边的优先级比较方法是，边的端点中优先级较小的点进行比较，点的优先级低的对应边的优先级低，如果这个值相等，则标签个数少的边优先级低；

D4：维护发生变化的边的捷径域，对于同一起止点下的两条边e和e′，如果边e的边权小并且标签限制更少，即w(e)≤w(e′)并且

D6：鉴于只对减小的边进行直接更新，对增加的边暂不做更新，所以对于增加的捷径e，重新计算e的权重，再维护e的捷径域；而对于e减小，直接维护e的捷径域；

D7：一个层级的边更新完成后，再更新下一个层级的边；所有层级边更新完毕后，得到更新后的CHLR索引图。

通过多维度实验验证本发明的有益效果，具体包括：

1、随机抽取1000条边进行更新，比较所述的前三种方法平均每条边更新所用时间；

2、一次性将图上0.1％-100％的边进行批量更新，比较所述的四种方法以及重新构建索引方法所需总时间；

3、比较所述的前三种方法中实际发生变化边的数量与重新计算边数量的比值，即命中率。

其结果显示：

第一个实验是记录在增加以及减小不同比例情况下更新索引所用时间，在增加和减小边权重的情况下，所述的第二个方法和第三个方法更新时间在100毫秒，可见提出的方法可以高效维护基于带标签路网的最短路径索引。所述的第二个方法和第三个方法相较于第一个方法可以提升2个数量级，因为所述的第二个方法可以避免大量不必要边的遍历和计算，第三个方法最快，因为它进一步减少了对未发生变化边的计算，从而进一步提升更新效率。此外，在不同更新比例下，所用时间差别不大，说明本发明提出的各方法随着边权的变化有很好的扩展性。

第二个实验给出了批量更新所用时间的分析结果，将图上0.1％-100％的边进行更新，记录所需时间，本发明所述的第二、三种方法比第一种方法快得多，而本发明所述的第四种方法可以进一步提升维护索引效率当图上0.1％的边发生变化时，第四种方法相较于重新构建索引所用时间提升了3个数量级。

第三个实验讨论了不同方法的命中率，命中率是指实际发生变化边的数量与重新计算边的数量的比值，随着更新边数的增加，命中率也在增加，因为更新的边数越多，实际发生变化边的数量就越多。本发明所述的第二、三种方法比第一种方法命中率更高，第三种方法命中率高达80％以上，说明本发明提出的方法可以高效维护带标签路图的最短路径，减少很多对未发生变化边的不必要计算。

附图说明

图1为实施例原图；

图2为基于图1的CHLR索引图；

图3为本发明方法2更新过程示例图；

图4为本发明方法3更新过程示例图；

图5为边权重减小情况下平均运行时间结果图；

图6为边权重增加情况下平均运行时间结果图；

图7为批量更新所需时间结果图；

图8为发生变化的边占重新计算的边的命中率结果图。

具体实施方式

1)带标签路网最短路径索引图的构建

MichaelRice等人在《Graph indexing of Road Networks for Shortest PathQueries with Label Restrictions》一文中给出了带标签路网上构建CHLR最短路径索引图的方法。对于有向、带权、有标签的路网G＝(V,E,w,Σ,l)，V和E分别是点集和边集。Σ是用来表示标签的字符集，w是图上边的权重函数，l是将边和标签进行关联的函数，给图上的点分配优先级φ(v)。引入的一条捷径可以表示为((u,v),w,l)，图上的一条从点s到t的路径表示为P

对于图G和一个标签限制集合，一条符合限制条件的最短路径应该满足：该路径各边上的标签和标签限制集合没有交集，也就是说沿着这条路径不会违背限制条件，并且它的权重是最小的。

构建CHLR索引，需要引入“捷径”这一概念，收缩点q相连的两条边e′＝(u,q)和e″＝(q,v)，并且φ(q)<φ(u),φ(q)<φ(v)，如果没有一条比P＝(e′,e″)更短的路径P′满足φ(P)<φ(P′)并且

根据点的优先级依次收缩各点，如收缩点q时，找出q的邻居中，优先级比它大的点所连结成的边，两两一对找出e′＝(u,q)和e″＝(q,v)。在优先级比q大的点构成的子图中调用Dijkstra算法，查询是否有更短且符合标签限制条件的路径P′，如果找不到这样的P′，那么引入捷径(u,v)。通过这样的方法，可以得到引入捷径后的图G′。

图1是原图，圆形表示一个点，V的下标是点的序号，每个点旁边方框内数字是这个点的优先级，边上有边的权重和标签信息，表示为(权重，标签集合)。以收缩点V

在引入捷径后的图G′进行最短路径搜索，要找出s到t且不经过限制集合R中标签的最短路径，具体方法是：将它分为前向图G

实施例1

本发明的一种基础方法即方法1

对于图2上的CHLR索引图，采用方法1进行动态维护，如果一条边((v

对于构建好的CHLR索引图，需解决的问题是当图上边的权重增加或减小以及边上的标签发生变化的时候，如何对CHLR索引进行维护更新。

一种基础方法即所述方法1，是找到所有受影响的边并重新计算，这里的边也包含引入的捷径，主要分为两个步骤：(1)找到所有受影响的边。具体方法是，当改变边e＝(q,v)时，假定φ(q)<φ(v)，通过收缩点q而产生的捷径(u,v)可能受到影响，因为如果是(q,v)和(u,q)产生的(u,v)，那么(q,v)的变化就可能影响到(u,v)，这时需要重新收缩点q来计算捷径(u,v)新的权重和标签，把需要重新收缩的点q放入存储所有需要重新收缩计算的点的集合θ，而(u,v)又可能影响到其他的捷径，所以u和v中优先级更低的点也需要加入集合θ，来继续传递本次变化带来的影响。(2)重新计算边。找到了所有受影响的边之后，重新计算边权重的方法就是对产生边的顶点进行重新收缩，也就是对集合θ中的点重新进行收缩操作，重新构建捷径，从而得到更新后边的权重和标签。

对于一条发生变化的边，需要遍历它的所有邻边来找到这条变化的边所能影响到的捷径，这需要O(d

实施例2

本发明的一种新的维护CHLR索引的算法即方法2

对于图2构建好的CHLR索引图，采用方法2进行动态维护。图3展示了邻居关系图，每个长方形表示索引图中的一条边，方框内上面的粗体数字对表示这条边的起止点，下面是这条边的权重和标签集合，表示为(权重，标签集合)；一对父母通过有向边连接到同一个圆形的连接节点，连接节点指向这对父母的孩子；发生变化的边所在的方框线条加粗。当边e

本发明提出一种新的维护CHLR索引算法，来避免对未发生变化的边的重新计算。首先需要说明一些辅助本算法的概念，对于一个构建好索引的路网，给定边e＝(u,v)和e′＝(u,q),e″＝(q,v)，如果φ(q)<φ(u),φ(q)<φ(v)并且l(e)＝l(e′)∪l(e″)，那么e′和e″称为e的父母，e是e′和e″的孩子，e′是e″的伴侣。可以发现，一条捷径可以有多对父母和多个伴侣，但是一对父母只能有一个孩子。

一条捷径可以是原图的一条边本身，也可以是由它的一对父母收缩而得到，所以捷径的权重是原图边的权重和它所有父母权重之和的最小值。基于此，计算捷径权重的算法是，捷径权重需要初始化为无穷，如果原图有捷径这条边，那么它的权重是原图边权重，接下来检索目标捷径的每对父母，看各对父母是否能产生更短的权重，如果能，需要更新捷径的权重值。支持量这一概念将在后文进行介绍。

方法2中的计算捷径权重算法

通过构建CHLR索引的过程可以发现对于相同起止点下不同标签的各边也会互相影响。对于同一起止点下的两条边e和e′，如果w(e)≤w(e′)并且

方法2中的维护捷径域算法

/>

对于一条发生变化的捷径e，需要维护它的捷径域，即所有与它相同起止点不同标签下的捷径。如果有可以覆盖e的捷径，那么就不再需要e，权重置为无穷，e加入相应捷径的覆盖集合。如果e仍然保留，那么需要根据e的变化类型是增加还是减小分类讨论。如果是增加类型，那么原本被e覆盖的捷径可能随着e的增加不再被覆盖，因此对于e的覆盖集合所有捷径重新计算权重，如果权重比e的小，那么将不再被e覆盖，需要重新加入图中并对边权重进行维护。对于减小类型，可能e会覆盖更多的边，对于所有相同起止点下标签是l(e)超集的边进行遍历，如果权重比当前的e大了，那么e会将它覆盖，被覆盖的边权重置为无穷。

为了对CHLR进行维护，本发明提出一种链式更新算法，目的是尽可能只处理发生变化的边，将变化的边进行链式传播，既然所有捷径都是由父母收缩而成，因此边权重的变化只会传播影响到它的孩子。当w(e)减小，只需要看这个更小的值是否会给它的孩子带来更小的权重，如果会，那么更新即可；当w(e)增加，需要重新计算它的孩子的权重，这是因为如果该孩子的边权重是由e收缩而得，那么w(e)的增加可能会使得该孩子的权重不再被支持，所以需要重新计算当前情况下孩子的边权重。所有发生变化的边会被插入一个优先队列，优先队列基于边的优先级进行更新，判断优先级的方法是：对于两条边，端点较小的点之间进行优先级比较，优先级更小的点所对应的边优先级也更低，如果这个值相等，那么标签数量少的边优先级更低。

通过CHLR构建方法，以及父母、孩子的概念，可以发现孩子捷径的优先级是比父母捷径优先级高的，按照优先级从低到高更新，可以保证每个孩子更新前，它的所有父母都已经完成了更新。并且，一条捷径的变化只会影响到比它优先级更高的孩子，所以当捷径的权重减小，只需要看是否会给它的孩子带来更小的权重；而捷径的权重增加时孩子当前的边权重可能已经不再被支持，所以需要重新计算孩子的权重，通过边的优先级从低到高依次链式传播更新可以保证更新结果的正确性。除了链式传播更新过程，还需要注意的是通过维护捷径域算法维护发生变化的捷径域。

方法2即一种新的CHLR维护算法

为了维护CHLR，需要初始化一个存储所有发生变化的边的优先队列Q，如果边的标签发生变化，相当于旧标签下权重置为无穷，新标签下边权重置为新的权重。首先重新计算旧标签下捷径权重，如果这个捷径权重更大了，那么将它加入优先队列Q，并使用维护捷径域算法维护好旧标签下的捷径域。如果新的权重小于当前新标签下捷径权重，那么更新新标签的边权重，加入优先队列Q，并使用维护捷径域算法维护好新标签下的捷径域。如果标签没有发生变化，那么只需要重新计算当前标签下新的捷径权重，并根据增加或是减小的类型加入优先队列Q，并使用维护捷径域算法维护好当前标签下的捷径域。

对于优先队列Q中的各个边依次进行更新，每次有一条捷径发生变化时，需要找出它所有的孩子，当变化类型是增加并且当前孩子权重不为无穷时，需要重新计算孩子的权重，来看它的权重是否已经不再被支持，如果新的捷径权重增加了，那么孩子捷径加入优先队列Q，并使用维护捷径域算法对发生变化的孩子捷径域进行维护。当变化类型是减小，只需要重新计算当前边作为父母之一的时候权重和是否会赋予孩子一个更小的边权重，如果会的话，就对孩子的权重进行更新，并插入优先队列Q，同时也需要使用维护捷径域算法对发生变化的孩子捷径域进行维护。

实施例3

本发明的一种CHLR索引维护优化算法即方法3

对于图2上的CHLR索引图，采用方法3进行动态维护，图4给出了针对图2带捷径支持量的邻居图，当边e

本发明提出了一种CHLR索引维护优化算法，进一步减少对非必要未发生变化的捷径的重新计算和维护。首先需要引入捷径的支持量这一概念，所谓捷径的支持量，就是指支持当前捷径权重的情况数，这包含两部分，如果捷径所对应原图存在一条这样权重的边，那么原边是支持当前捷径的一种情况；第二部分是对于捷径的所有父母中能支持当前捷径权重的父母对的数量。这两部分构成了捷径边权重的支持量。

可以发现，只有发生变化的边是支持当前孩子权重的情况时，边的变化才可能影响到这个孩子，所以只需要考虑变化的边原权重是支持当前孩子权重的情况，只有这种前提下才需要重新计算这个孩子的捷径权重，否则的话，该边的变化是不会影响到这个孩子的。此外，即便在变化边的原权重是支持当前孩子权重的条件下，还需要考虑孩子捷径的支持量，如果支持量值大于1，那么说明不止有一种情况可以支持当前孩子捷径的权重，因此即便当前边的权重增加了，会不再支持这个孩子捷径的权重，但是还会存在其他的父母对当前孩子捷径权重予以支持，所以也无需重新计算孩子捷径的权重，只需要将当前孩子捷径支持量减1即可，表明支持这个孩子捷径权重的情况减少了一种。总的来说，当一条边的权重发生变化，对孩子进行遍历时，如果它不支持当前孩子的权重，或者当前孩子捷径支持量大于1，那么都无需重新计算这个孩子的权重。

方法3即CHLR索引维护优化算法

/>

对于CHLR索引维护优化算法，需要维护捷径支持量，当标签发生变化时，如果旧标签下原边的权重等于捷径权重，说明图上的原边是支持当前捷径的一种情况，如果它的支持量小于2，则说明当旧标签下原边权重更新后，不再有支持这条捷径的情况存在，所以需要将支持量置为0，并插入优先队列Q进行更新。如果新的权重等于新标签下捷径权重，说明新的边权重也可以支持这条捷径，则捷径支持量加1表示多了一种支持情况。如果新的边权重小于新标签下捷径权重，说明更新后边权重更小，则需要更新新标签下的捷径权重为边权重，并插入队列Q。如果标签没有发生变化，仍是旧标签下，考虑如果原边权重是旧标签下捷径的权重，则支持旧标签下捷径支持量减1；如果新的权重等于旧标签下捷径的权重，则支持旧标签下捷径支持量加1；如果新的权重小于旧标签下捷径的权重，则说明存在更小的原边权重对该条捷径进行支持，所以更新捷径权重，并将支持量置为1，变化的边插入优先队列Q；如果新的权重大于旧标签下捷径的权重并且捷径支持量小于1，说明不再有支持原捷径权重的情况，并且边权重增加了，所以需要将捷径支持量置为1，并插入Q。

对优先队列Q各边根据优先级依次进行链式更新，对于发生变化的边e，找出所有邻居伴侣和它们的孩子来传播更新。如果是e增加并且孩子权重不为无穷，那么判断孩子捷径支持量是否大于等于1并且当前e和它的伴侣是支持这个孩子捷径权重的一对父母，如果满足，那么e即将增加从而不再支持这个孩子捷径的权重，因此孩子捷径支持量减1，，如果此时孩子捷径支持量小于1，说明不再有支持这个孩子捷径权重的情况存在了，因此孩子捷径的权重会增加，插入队列Q。当e减小，如果减小后的e和它的伴侣恰好支持这个孩子捷径权重，则孩子捷径支持量加1，表示又多了一种支持当前捷径权重的情况。如果减小后的e和它的伴侣权重和小于这个孩子捷径权重，则更新孩子捷径权重，并将孩子捷径支持量置为1，孩子捷径减小了，需要插入优先队列Q。

通过上述过程可以发现，当边权重减小时直接进行更新传播影响，看是否会产生更小的孩子捷径；但是当边权重增加，则暂不做更新，这是因为需要保留原来权重来看是否变化的e原边权重是支持孩子捷径权重的一种情况，从而结合孩子捷径支持量判断孩子捷径是否会发生变化。因此在算法最后对增加的边才进行重新计算，对于增加情况，重新计算e的权重，并维护e的捷径域；对于减小情况，则只需直接维护e的捷径域。

对于CHLR索引维护优化算法，只有发生变化的边才会被插入优先队列Q，而插入过程需要根据优先级进行，这需要O(|E

实施例4

本发明的一种批量维护CHLR索引的算法即方法4

对于图2构建好的CHLR索引图，根据方法4，首先给边分配层级，对于边((v

批量更新指对多条边的同时更新，为了维护CHLR索引，首先需要给边分配层级数，具体方法是，对于构建好CHLR索引的图，如果一条捷径的孩子集合是空集，那么这条捷径的层级数是1；否则，这条捷径的层级数是它所有孩子捷径的最大值加1。

根据上文结合层级数定义方法，可以发现同一层级的捷径之间不会互相影响，因为一条边的变化只会影响到它的孩子捷径，而父母的层级一定比孩子高。对于批量更新，按照层级数从高到低进行更新，可以保证每条捷径更新前它的所有父母都已经完成了更新，从而保证了更新结果的正确性。

借助桶这一数据结构，每个桶存储一个层级下需要更新的边，按照层级从高到低依次更新各桶的边，一个层级完成所有更新后，再处理下一个层级中需要更新的边，新发生变化的边插入到相应层级的桶中。

为了展示本发明提出的维护CHLR方法效率，从多维度进行了一些实验，实验数据集来自DIMACS，这其中包含大量真实路网数据集，本发明采用实验的数据集具体细节如表1所示。

表1数据集具体细节

第一个实验是记录在增加以及减小不同比例情况下更新索引所用时间，横轴表示变化的百分比，纵轴是更新索引所花费的时间，记录方法是随机选取1000条边进行更新，计算平均每条边更新所用时间。实验结果如图5和图6所示，每张图上的八张子图从(a)到(h)分别是对应于表1中数据集NV到US上的运行结果；基础算法是在发明内容中第一项提出的；新的维护索引算法是发明内容中第二项提出的；CHLR索引维护优化算法是发明内容中第三项提出的。可以发现在增加和减小边权重的情况下所提出的方法2即新的维护索引算法和方法3即CHLR索引维护优化算法相较于方法1即基础算法可以提升2个数量级，因为本发明提出的方法2即新的更新索引算法可以避免大量不必要边的遍历和计算，方法3即CHLR索引维护优化算法速度最快，因为通过优化手段进一步减少了对未发生变化边的计算，从而进一步提升更新效率。此外，在不同更新比例下，所用时间差别不大，说明本发明提出的方法随着边权的变化有很好的扩展性。

第二个实验给出了批量更新所用时间的分析结果，将图上0.1％-100％的边进行更新，记录所需时间，批量维护CHLR索引算法是发明内容中第四项提出的，其他算法是将发生变化的边逐一进行更新处理，实验结果如图7所示，每张图上的八张子图从(a)到(h)分别是对应于表1中数据集NV到US上的运行结果。可以发现，本发明提出的方法2即新的维护索引算法和方法3即CHLR索引维护优化算法比方法1即基础的维护索引算法快得多，而本发明提出的方法4即批量维护CHLR索引算法可以进一步提升维护索引效率。

第三个实验讨论了不同方法的命中率，命中率是指实际发生变化边的数量与重新计算边的数量的比值，结果如图8所示，每张图上的八张子图从(a)到(h)分别是对应于表1中数据集NV到US上的运行结果。随着更新边数的增加，命中率也在增加，因为更新的边数越多，实际发生变化边的数量就越多。本发明提出的方法2即新的维护索引算法和方法3即CHLR索引维护优化算法比方法1即基础的维护索引算法命中率更高，说明本发明提出的方法可以减少很多对未发生变化边的不必要计算。