时间依赖网络模型实现最佳行程的精确排课算法

理论计算机科学电子笔记92（2004）3-15www.elsevier.com/locate/entcs时间依赖网络模型实现快速精确排课Gerth Stølting Brodal1奥胡斯大学计算机科学系，纽约，DK-8000，ArhusC，Denmark。Riko Jacob2苏黎世理工大学计算机科学研究所摘要我们考虑用于精确时间表查询的高效算法，即为使用火车系统的旅行者找到最佳行程的算法。 我们建议使用时间依赖网络作为模型，并显示这种方法的优势，时空网络作为模型。关键词：时刻表，时变网络，最短路径，出行者信息系统，建模，算法1介绍为使用公共交通的旅行者找到最佳行程是一项算法挑战。使用标准算法来解决行程查询的时间表有趣的细节和大小很容易导致无法接受的缓慢的答案，即使在现代计算机上。在实践中，这个问题是通过使用启发式求解器来克服的，即快速计算结果的求解器，不能保证是最优的。我们的重点是制作最佳行程。1BRICS（计算机科学基础研究，www.brics.dk，由丹麦国家研究基金会资助），电子邮件 ：gerth@brics.dk ， 由 欧 盟IST 计 划 部 分支 持 ， 合 同 号IST-1999-14186 （ ALCOM-FT）。2 电子邮件：rjacob@inf.ethz.ch，在金砖国家期间完成的工作。1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2003.12.0194G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-最优行程查询的本质是最短路径问题。解决这个问题的自然方法是将时间表转换为某种加权图（建模为时空图[9，10]），在该图上，最短路径对应于最佳行程。这似乎是一个标准的方法，例如[11，6，12]。 在这种情况下，我们建议使用时间相关图而不是加权图作为模型。这种模型更接近于时间表本身，并允许算法立即忽略时间表的大部分时变网络的关键思想是链路的时延取决于链路使用的时间点。这种模型在其他几种情况下也很自然，例如互联网上的数据包或道路网络上的汽车。这模拟了链路引起的延迟取决于用于到达该链路的路径的现象。一般来说，在这种网络上的最短路径问题很难回答，但重要的特殊情况下允许快速算法。这些类型的网络已经在文献中被考虑过，例如参见[7，8]的调查。在[1]中描述了使用这种类型的建模来路由乘客，其中重点是在道路网络上使用汽车的旅行者在[11]中，作者提出了一个问题，即计算德国铁路系统的最佳行程是否可行。这个问题也是[12]中的例子。他们提出了几个启发式的运行时间的改进，允许快速的答案。我们的建模是兼容的这些算法，他们可以立即应用于时间相关的算法。我们预计，我们的建模和算法方法将导致显著的运行时间改善，从而允许更大或更详细的网络（包括本地总线，扩展到整个欧洲）。 因为我们缺乏 我们的方法的分析是与[11]的理论比较。在[12]中考虑的网络的修改也只修改了所用图的站方面，我们在这里提出的算法可以很容易地采用[12]的加速技术我们还考虑了算法问题的扩展，允许限制传输。对问题规模和现代硬件的简单计算表明，预先计算所有可能查询的答案并将结果存储在硬盘上是可行的。如果网络规模允许这样做，它可以成为算法解决方案的可行替代方案。如果网络不太大，应该是这样。当然，这种方法仍然需要在预处理步骤中找到快速1.1算法问题如前所述，我们希望能够为乘客提供最佳行程。 也就是说，考虑到全国所有火车的时刻表，我们希望 以某种方式预处理这些数据，使我们能够快速回答查询。我们考虑以下形式的查询：G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-5--≤∈∈t，他最早什么时候能到B站，（怎么实现）？”为了简单起见，我们假设换乘列车没有任何诱发成本，即不需要时间，并且可以根据需要经常进行。(We将在第5节中讨论更详细的建模。）我们假设我们有一个表示时间的集合T，就像实数，整数（例如，自1.1.2000以来的秒数），或设置0：00，0：01，...，二十三点五十九分我们只假设T中的元素有一个全序。有时我们还假设存在一个定义在T上的加法运算。时刻表T是一组列车连接。它在一定的时间范围内是有效的.这是一个T的区间。事件是一个对（a，t），其中对于某个有限的站集合S，T. 列车连接是一对（e1，e2），e1=（a1，t1）出发事件，e2=（a2，t2）到达事件。我们知道到达事件的时间不早于离开事件的时间，即t1t2。T中的行程是事件序列，更确切地说是列车出发和到达事件e1，e2，.的交替序列，E K。两个事件e2i-1，e2i必须是T中某列列车的连续出发和到达事件，两个事件e2i，e2i+1必须是同一车站的到达和出发事件常见的是，T没有明确给出，而是作为例如一天的时间表和这一天在某个时期内重复的附加信息请注意，在周期性计划中，如果地平线被限制为一天，则将存在不可能的过夜连接。这些定义有一些严格的限制。在一个车站，我们无法区分继续在同一列火车和转移。我们也不允许旅客使用任何其他交通工具，如步行200米从一个站到另一个。在第5节中，我们将解决这些问题，允许我们对换乘的最大次数施加限制，或者将在车站内步行所需的时间作为换乘的一部分。2利用时空网络我们在这里描述的方法是直接给出我们如何使算法问题精确。 它是一个直接的时间表转换成一个有向加权图。这个图中的路径几乎是路线。为了计算权重，重要的是T允许加法和减法。给定一个时间表T，我们用以下方式构造图G=（V，E）：V是T的所有事件的集合。 从站点a的事件e到e之后站点a的第一个事件之间存在一条边。 如果时间表是周期性的， 通过具有从站A处的当天的最后一个事件到站A处的当天的第一个事件的链接而被反映。 如果一对事件（e1，e2）在T中，则存在从e1到e2的有向边。加权图模型中边的权重由其端点的时间差给出，即，行进时间6G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-或在车站等待的时间这种类型的模型可以被看作是一个时空网络，如[9]中所描述的它是[11]中使用的模型，因此对我们很重要，因为我们将在第4节中使用它进行运行时间比较。在[11]中，使用了该模型，并使用不同的算法进行了增强，以提高运行时间。这些算法立即转换为时间相关的方法，并实现运行时间，允许在合理的时间内为德国铁路系统的因为我们可以严格地改进这个模型，所以这个可行性声明仍然有效。这两种方法的详细比较在第4节中给出。我们也有理由相信，我们的方法扩展性更好，因此我们希望它在更大或更详细的网络上足够快，例如，包括当地的公共汽车和火车，以及/或精确地改变火车。在[11]中，作者观察到“CPU时间与数字呈线性关系，”（《易经》卷一）：“。此语句可以用缓存行为来解释。如果我们假设优先级队列保持足够小以适应CPU缓存，而图太大了，我们得到CPU时间由对应于访问图的缓存未命中主导。请注意，有一些明显的替代这个模型。例如，如果乘客实际上可以根据到达/离开事件的组合来改变列车，则可以偏离在一个车站处的边的循环并且明确地这个模型通常使用更多的边，但它允许更详细的建模。例如，我们可以确保车站内的步行实际上允许换乘。3时变网络在本节中，我们将开发时间依赖网络（或图，这是完全相同的）的术语，并证明最快路径算法的正确性我们省略了讨论的可行性最短路径问题在更一般的设置，允许负延迟和/或非单调函数。在这个更复杂的设置中，指定等待策略很重要。参见[7，8]，了解这种类型的网络的讨论。时间域是一个线性有序集T。在本节中，我们不假设存在定义在T上的加法运算。集合T的典型例子是实数和整数，但有限集合也很有趣。时间依赖网络是一个有向图G=（V，E），其中每条边e都有一个相关的链路遍历函数fe：T →T。设f：T→T是一个函数。 如果fJ满足f（t）≥t，我们说，f具有非负延迟。 如果对于t≤t，我们有f（t）≤f（tJ），我们说f是G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-7∈∈∈∈∈×∈∞∈→∈∈∈单调的这里我们使用G中时间路径的以下简单定义：序列v1，v2，.，v k V和序列t1，t2，.，如果e =（vi，vi+1）E是G的一条边，且ti+1= fe（ti），则t k T的时间构成一条时间路径.顶点v1被称为出发点或路径的源，t1是出发时间，vk是目的地，tk是到达时间。对于源节点s、目的地d和离开时间t的最早到达问题要求从s到d的到达时间最小的定时路径p类似地，如果我们固定到达时间的上界，那么最近出发问题也得到了很好的定义，即我们在到达时间不晚于指定到达时间的约束下，要求一条最迟出发时间为s的假设我们可以（有效地）计算一个图，并（有效地）执行T中元素的比较。然后，考虑Dijkstra算法的变体来解决最早到达问题是合理的。将其运行时间分析为T上的（基于比较的）优先级队列的函数求值、比较和操作的数量是很自然的。引理3.1（所有最早到达路径都是简单的）设G是一个具有单调非负延迟边遍历函数的有限时间依赖网络. 设p是G中的一条时间路径，在时间t离开节点s，在时间tJ到达节点d。则在G中存在一条简单的时间路径，时间t到达节点s，并在时间tJj到达节点d，使得tJ J≤ tJ。推论3.2（最早到达路径是明确定义的）设G是一个有限的时间依赖网络，具有单调和非负的延迟边遍历函数。设s和d是G的两个节点，出发时间为t T. 则存在在从s到d的所有定时路径上达到d处的最小到达时间的t j T。标签设置算法该算法是一个已知的修改Dijkstra的最短路径算法。我们这样说是为了完整。令Q是来自VT的对的优先级队列，其允许从T提取具有最小元素的对，即用节点注释的时间点的优先级队列。1：静态输入：G=（V，E），并且对于每个eE，单调、非负延迟链路遍历函数f e：TT。2：动态输入：源节点s V，目的地节点d V，出发时间tT3：a[v]：=对于所有v V4：a[s]：=t5：S：=S6：Q：={（s，t）}8G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-联系我们∞联系我们∈/∈7：当Q=do时8：（u，t，J）：=提取最小值（Q）9：S：=S u10：如果u=d，则11：对于每个边（u，v）E，使得v S做12：tJ：=fuv（a[u]）13：如果 a[v]>tJ，则14：如果a[v]=则15：插入（Q，v，tJ）16：其他17：update（Q，v，t，J）18：如果结束19：a[v]：=tJ20：pred[v]：=u21：如果结束22：结束第23章：结束24：v：=d25：p：=（v，a[v]）26：whilev sdo27：v：=pred[v]28：p：=（v，a[v]）.p29：end while30：输出：p上述算法对于单调、非负延迟的链路遍历函数是正确的。这是基于相同类型的参数作为一个显示Dijkstra的算法正确的非负加权图。正确性的证明可以在[3]中找到3.1基于时间依赖网络的时间表查找模型设T为时间表。我们描述了如何构造一个时间依赖网络G=（V，E，f）。我们选择节点集合V作为出现在T中的站点集合。设u和v为两个站。德费恩C uv=，（t，tJ）|.（u，t），（v，TJ）<$∈T，也就是说，对于从u到v的每一个直接连接，在Cuv中存在一对时间。如果Cuv为空，则从u到v没有弧。 否则，我们定义f uv（t）= min {tJJ|（TJ，TJJ）∈C uv且t≤ TJ}.该函数是单调的，具有非负时滞。让我成为一个旅程。然后，我们在G中找到一条时间路径p，它在某个站点上永远不会晚于I。因此，路径p是一条定时路径，它到达目的地的时间不会晚于I。G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-9−设p是G中的时间路。通过定义链路遍历函数，我们知道，p的每个链路遍历对应于T的一个条目。将这些条目连接起来会生成一个有效的行程。总而言之，我们可以回答从时间t的s到T上的d的行程查询通过解决G上的最早到达问题，源s在时间t，目的地d。4执行问题有几种已知的加速技术用于Dijkstra算法。这类技术有两类，即On-the-Money势和修剪，例如[11，12]中所使用的一种众所周知的潜在技术是修改所使用的值通过到目的地的剩余路径长度上的下限在优先级队列中进行。如果网络嵌入到平面中，则这可以是到目的地的欧几里得距离的适当乘法。说服自己这种方法正确性的一种方法是考虑根据某些势修改图的边权重，即wuJv=wuv+p（v）p（u）。给一个图添加一个新的点不会改变图中路径的相对权重-如果路径p比G中的路径q长，则路径p也比GJ上的路径q长，图具有修改的权重。添加一个不产生负权重的势并不影响Dijkstra算法的正确性。如果我们巧妙地选择势，我们可以显着提高算法的运行时间。如果我们碰巧使用到d的最短路径距离作为势函数，p，我们得到恰好所有在到达d的最短路径上的边的权重为0。如果最短路径恰好是唯一的，则算法只查看最短路径上的节点和这些节点的传出边。这种情况当然不是我们期望找到的，如果我们已经有了最短路径的潜力，我们甚至不需要Dijkstra 但如果我们有一个好的保守近似， 我们希望能够显著减少算法检查的图形部分。当然，只有当这个势可以容易地计算时，这才是有用的。例如，这对于到目的地的欧几里得距离是正确的。另一种更直接的减小图的被检查部分的大小的方法是移除不相关的边和节点，即，而不是当前s和d的最短路径。在极端的情况下，我们可能已经预先计算了所有可能的s和d的最短路径，并存储了结果路径。现在我们可以忽略所有不在当前路径上的边。然后算法将只探索路径本身。同样，在这种情况下，不再需要运行算法。这种方法的有趣之处在于，我们不需要大量的内存来存储预计算的结果，并且评估链接是否可以被忽略很容易。一个很好的例子是使用的修剪技术10G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-在[11]中。对于每条边，我们都有一些几何信息，这些信息与边的s和d有关。在[11]中指出，这些加速技术的组合减少了时空网络中Dijkstra算法的运行时间，足以在线计算完整的德国铁路时刻表上的最佳行程。我们观察到，这些加速技术在时间依赖网络上同样强大，并且使用时间依赖方法可以显着减少网络的检查部分的大小，从而减少优先级队列的大小下面我们将分析不同的时间表查询算法的运行时间。这是作为一个比较的空时图的算法，然后不同的实现的链接遍历功能。确定运行时间的参数为• 图中被检查部分的大小（以节点为单位），这是算法用估计值和树边进行注释的地方，即算法第3行中的节点v• 图形中被检查部分的边的大小。这是内存访问/功能评估。• 优先级队列• 最小提取操作数。 这是我们探索节点u，即，在算法的第3行中，我们知道节点是u这里我们不考虑算法维护优先级队列所花费的时间。在文献中有几个结果讨论了如何在这种情况下获得快速优先级队列，例如使用边权重是整数的事实这种优先队列也可以用于时间依赖的网络，只要我们把时间限制为整数。我们注意到，即使是对所提出的最短路径算法进行更大的修改， 在[5]中的方法可以很容易地结合到时间相关算法中我们考虑从时间t的s到d的时间表查询。设tJ为最快行程到达d的时间4.1比较的基础：时空网络算法我们在时空网络上运行Dijkstra算法。我们观察到，我们从不更新任何节点v的距离估计（a[v]）。这是因为节点有一个内置的时间，我们在所有可能的路径上都同样快地到达它。这可以用来加速优先级队列。考虑一个站A。该算法从最早的事件开始，到达时间为a到tJ。这些事件实际上有多少在很大程度上取决于车站。 但是我们可以看到，对于一个长的行程，即对于大TJ，是徒劳的工作的可能性：假设s本身是一个繁忙的车站，每小时有10个城市的不间断连接。假设tJ是t后4小时。然后，我们有效地探索了t之后第一个小时内10个连接的事件。但是之后我们继续探索s处的节点，G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-11||弧的另一侧已知是可到达的（但推测在Q中还不可到达）。其他算法以其他代价避免了这些无用的探索步骤。这种交易是我们在下面调查的4.2一般分段线性函数如果我们采用模块化的方法，我们将实现链接遍历功能完全相互独立。也就是说，我们将有一个过程，产生给定t的值fuv（t）。如果k是从u到v的连接数，即k=Cuv，则这可以很容易地通过log2（k）比较来实现。现在我们不需要探索节点，但是我们可以考虑时空网络中没有考虑的弧，因为离开事件在tJ之后。此外，我们浪费时间做独立的搜索不同的外出弧。请注意，当时间表基本上是周期性的时，这种方法可以轻松地处理大的时间范围，但有许多例外情况任意分布在时间表上。这种情况的重要特征是链接遍历函数具有小的（就空间而言）表示，这仍然允许快速求值。4.3合并搜索为了避免在第3-3行的for循环中重复搜索，可以将所有事件合并到一个数据结构中更准确地说，我们在每个节点上都有一个平衡的搜索树，它的叶子上有所有传出事件的时间。 在在预处理步骤中，我们为每个弧在时间上的下一个弧用传出事件的列表来注释这些叶。然后，每个节点的探索都需要一次二分搜索加上弧另一侧的更新操作这种方法仍然对每个节点执行一次搜索，并且它使用了额外的空间，在一个节点上，我们有一个乘法的出度爆破4.4避免空间开销（列表查找）设d是时间依赖网络中对应于a的节点的出度。为了避免空间开销，我们可以将一个站点a的所有传出事件放入一个数组A中，按它们的出发时间排序。我们可以这样做：我们放置d个这样的事件（所谓的主条目），然后我们留下d个空格，然后是接下来的d个事件，依此类推。让tJJ是一些空格之前的最后一个事件的时间。然后，我们将每个传出方向的tJJ之后的下一个事件放入A的到目前为止为空的条目（次要条目）。我们把所有的主要条目放在一个平衡的搜索树中。当我们探索节点a时，我们找到了A的下一个主条目，并扫描了A的下一个2d条目。 那么我们可以肯定所有接下来的事件在所有的外出方向中都在扫描的条目中。12G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-这种方法使用与时空图渐近相同的空间它仍然在每次探索节点时执行一次搜索。4.5避免搜索如果我们观察算法，我们会看到，当我们执行更新操作时，我们会处理时间表的事件对e。特别地，我们在一个特定的节点a处有一个特定的到达时间tJJ。除了e之外，我们还可以在a处存储一个指向传出事件数组的指针，即指向时间tJJ之后的第一个主元素。如果我们使这个指针成为存储在优先级队列中的数据结构的一部分，就不需要进行搜索来探索一个节点4.6避免考虑在tJ之后离开的连接还有一个方面，时空图可能优于时间依赖网络方法：它永远不会考虑出发时间在到达目的地站的时间tJ之后我们也可以在时间依赖网络中实现这一点假设我们做了不做节省空间的事情，也就是说，我们有一个节点上每个相关时间的传出事件列表。我们稍微改变了这个列表，使它不再按离开事件的时间排序，而是按到达事件在弧的另一边的时间排序我们并没有将列表中的所有到达事件一次插入到优先级队列中，而是只插入列表中的第一个事件和指向下一个事件的指针。只有当我们提取第一个事件时，我们才插入列表的第二个事件，依此类推。时间表比空间-时间图算法所做的，我们渐近地永远不会比那个算法做更多的工作4.7缓存行为即使如此，最后提出的算法是最快的算法，如果我们考虑渐近最坏情况下的运行时间的单位成本的RAM，它可能不是最快的在实践中。一件事是，在运行时间中节省常数因子的可能性是难以预见的，并且是实际运行时间中的一个重要因素。更重要的是，我们还应该考虑到，在真实机器上的运行时间可能会受到缓存故障的严重影响。在这方面，最后一个算法可能不是一个好主意：它可能会导致我们在优先级队列中放置的每个条目都有一个缓存未命中，而列表中的查找可以使用所使用条目的位置。另外，如果优先级队列足够小，可以放入缓存中，我们希望列表查找更快。实际的缓存行为似乎很难预测，如果不进行实验，就很难真正说明什么是最快的算法。我们留下这样的陈述，即应该有一些可能性来适应上述算法以适应特定的缓存大小。G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-13当然，在优化算法时还需要考虑优先级队列。如果时间表碰巧是这样的，优先级队列总是非常小，并且总运行时间由访问网络引起的缓存未命中主导，则4.8关于算法的结论我们可以将下一个事件的列表看作一个持久的链表，它（在预处理中）随着时间的推移而改变，而不是使用一个具有主条目和次条目的数组。关于这个想法的细节见[4]。这种构造给出了相同的渐近行为。它还有一个额外的优点，即它可以很容易地转移到第4.6节的勘探节约思想。我们可以看到这里介绍的所有算法都是一些聪明的方法，可以按需创建一些时空图的重要部分。这只是一个不同的观点。请注意，我们也可以解决给定到达时间的最新出发问题为此，我们只是颠倒了时间的方向和出发和到达的时间表。这里提出的所有算法都可以额外执行[11]中建议的在线网络修剪技术这里进行的理论分析表明，这里提出的算法应该比[11]中使用的显式时空图算法更快，在现实网络上可能要快得多如果我们使用这里提出的算法，这些算法足够快当然，只有用真实世界的数据进行实验才能得出结论性的答案，无论这些陈述是否真的成立。5扩展5.1更现实的转移到目前为止讨论的算法问题做出了不切实际的假设，即假设火车之间的转移不需要时间和成本。看起来，我们没有得到一个更现实的模型免费转让。首先，我们试图在行程中包括一些在车站内散步的时间，尽可能少地延长网络。我们认为每个平台都是自己的一个站。然后，我们通过步行连接连接站台，要么遵循车站的几何形状，要么用一颗星连接到车站的大厅。步行链路的链路遍历函数具有恒定延迟，即，对于反映步行距离的某个常数c，它们具有f（t）=t+c（这假设我们的集合T有加法。）14G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-−- -≥5.2限制行程上述列车变化的建模也可以用于计算变化的数量。在不进一步扩展网络的情况下，如果不涉及从一个站台移动到另一个站台，我们不会考虑更换列车。如果我们想更精确，我们可以引入虚拟平台，每个列车线路一个。然后，我们不捕获列车线路内的列车变化，这是没有限制的，因为它总是可以避免的。请注意，如果每个列车都必须被视为其自己的列车线路，则我们基本上返回到显式网络。为了找到所有帕累托最优解，即对于最早到达行程的转移次数的每个约束，我们做以下事情：首先，我们找到最快的路径，而没有变化数量的上限。这将有一些数量k的转移，并且是如果转移数量的界限是k的解决方案。 在最多有k 1，k 2，.的限制下，0个传输。我们取原始网络的k个副本（级别），其中所有的步行链路（即代表传输的所有链路）将级别i与级别i+ 1连接起来。在这个网络上，我们寻找从第一层的s到节点d的某个副本的路径。如果我们找到这个，我们找到了最多有k1次传输的最快路径，路径端点的级别l告诉我们实际上有多少次传输。请注意，最快的连接可能需要5次传输，但坚持4次传输比只进行2次传输要慢。然后我们删除上面的所有级别，包括l，并继续搜索剩余级别的d的某个副本。我们继续，直到我们找到一个解决方案，没有转移或我们发现，我们不能达到目的地与少于l转移。在实践中，我们可能希望停止这一过程，只要坚持很少的转移导致不合理的长旅行时间。5.3连接到正则表达式上面的过程可以看作是在正则表达式约束下搜索最快路径如果我们认为网络中的弧代表使用标记为t的列车和标记为w的传输链路，则约束正则表达式为（w<$t <$w<$）k。在一般的正则表达式约束下计算最早到达问题是很容易的（我们只需要构造一个不确定的有限自动机，并构建与网络的叉积）。这可能是一个强大的工具，表达不同种类的限制行程。参见[2]中关于将形式语言约束强加于（最短）路径问题的复杂性的讨论5.4关于延期的如果时间表是使用时空图建模的，则这里提到的扩展也适用我们在这里想说明的一点是，使用时间依赖网络作为模型实际上可以简化描述。G.S.布罗达尔河Jacob / Electronic Notes in Theoretical Computer Science 92（2004）3-15引用[1] 克里斯·巴雷特，基思·比塞特，里子·雅各布，戈兰·孔杰沃德和马达夫·马多夫。 道路网络中的经典和当代最短路径问题：TRANSIMS路由器的实现和实验分析。在ESA 2003，计算机科学讲义第2461卷，第126-138页[2] 克里斯·巴雷特，里子·雅各布，和马达夫·马多夫。形式语言约束路径问题。SIAM J.Comput. ，30（3）：809[3] 格特·斯托尔廷·布洛达尔和里子·雅各布时间依赖网络模型实现快速精确的时间表查询。技术报告ALCOMFT-TR-01-176，ALCOM-FT，2001年9月。[4] James R.放大图片作者：Daniel D. Sleator和Robert E. 塔扬 使数据结构持久化。在Proceedingsof the Eighteenth Annual ACM Symposium on Theory of Computing，第109-121页[5] 安德鲁·V·戈德堡。 一种简单的线性平均时间最短路径算法。 算法中- ESA 2001，第LNCS 2161卷，第230[6] MatthiasMüller-Hannemann和KarstenWeihe。在实际应用中，最短路径往往是可行在Algorithm Engineering，WAE 2001，卷LNCS 2141，第185[7] Ariel Orda和Raphael Rom。具有时间依赖边长度的网络中的最短路径和最小延迟算法。Journalof the ACM，37（3）：607[8] Ariel Orda和Raphael Rom。时间相关网络中的最小权重路径。网络：国际期刊，21，1991年。[9] StefanoPallottino和MariaGraziaScutell`a。运输模型中的最短路径算法技术报告TR-97-06，比萨大学，1997年第14期。[10] StefanoPallottino和MariaGraziaScutell`a。 运输模型中的最短路径算法Marcotte和S. Nguyen，编者，《均衡与先进运输模型》，第245-281页。Kluwer Academic Publishers，1998.[11] Frank Schulz，Dorothea Wagner，and Karsten Weihe. Dijkstra算法在线：公共铁路运输的经验案例研究。在Algorithm Engineering，卷LNCS 1668，第110-123页[12] Frank Schulz，Dorothea Wagner，and Christine Zaroliagis.铁路系统时刻表信息的多级图应用。计算机科学讲义，2409：43-？？，2002年。