这里的拓展其实暗示了Q_j中必须要存在所有可能dominate新label的所有label。如何保证这一点呢？我们在下一节中给出解决方法。
标记处理的顺序：字典排序在LS处理标记的过程中，我们是按结点顺序拓展标记的，所以对于一个结点的多个标记我们需要依照一个顺序进行处理。这个顺序最好能在拓展过程中揪出所有无效点，即一边拓展一边进行EFF查找。
在函数图像中我们用斜率k来表示统治关系，容易想到从左到右判断k，找出所有的k>=0的线段。转化过来，就是按照先比较T再比较C的顺序进行排序。因此，我们在存储标记的时候也考虑按先判断T再判断C的顺序存储，处理时从小到大处理。这就是所谓的字典排序。显然，这是一种全排序，满足我们的需求。
我们有以下三个命题：
字典序是为了配合dominate的判断而生的。这些都是类似剪枝的操作，以避免穷举。加了这两个操作以后，你在枚举的过程中，就会发现很多不可行的路径，一旦不可行，立马停止该路径的扩展。
我们将所有标记分为三个部分：
Q为永久标记的集合
P为已处理标记的集合。
T为未处理标记的集合。
我们按照字典序对所有标记进行排序处理，可以保证所有T中的标记无法dominate P中的标记。因为每一条边的时间d_ij都为正值，因此被拓展出的新标记必定排列在原标记后，无法再dominate原标记。dominate关系有传递性，依照归纳法可得，T中的标记无法对任意中的P标记进行dominate处理。
我们还可以利用P、Q、T的定义给出一个关系式：
在算法中我们可以利用这个式子来计算T。
算法流程与例子A simple example：
下面提供C++代码。栗子用的是上面的简单栗子，命名按照上述定义。理解了算法的流程后，代码本身并不难。这里的代码重点在配合讲解，作为一个参考，所以没有选择复杂的数据结构和语法技巧，有需要的朋友可以自己作为练习自己尝试。
欲下载本文相关的代码及算例，请关注公众号【程序猿声】，后台回复【SPPTWCPP】不包括【】即可