LS算法通过迭代过程对label进行逐步修正，每次迭代均选择候选结点集中标号最小者退出候选结点集，并将该结点标号从临时标号转变久为永久标号。这是一种基于贪心策略的最短路径算法，每一次转化为永久标号的label都代表到当前结点的最短路径，考虑的是“当前最优”。
LC算法在每次迭代时并不一定将任何结点标号从临时标号转变为永久标号，只是对临时标号进行一次修正，所有结点标号仍然为临时标号；只有在所有迭代终止时，所有结点标号同时转变为永久标号。LC算法考虑的是“最终最优”，最短路径需要等待多次迭代直到整个算法运行结束才能被确定。
我们主要介绍LS算法。这里介绍解决不带时间窗约束的最短路问题的Dijkstra算法。该算法中，对于节点i，其label是(C[i], p[i])，其中C[i]表示从起点到节点i的最短距离，p[i]记录在d[i]距离下，从起点到节点i的路径中，节点i的前一个节点编号。s_0表示起点。c_ij表示通过边（i,j）的距离。执行流程如下：
Step0：初始化。令S为空，S*=N，C[s_0]=0，p[s_0]=-1；对N中的顶点i(i≠s_0)令初始距离标号C[j]=∞。
Step1：边界判断。如果S=N，则C[j]为最短路径长度，其最短路径可以通过p[j]所记录的信息反向追踪获得。结束。否则继续step2。
Step2：更新标记。从S中找到总花费最小的结点i，把它从S中删除，加入S。对于所有从i出发的可到达的后继点j，若C[j]>C[i]+c_ij，则令C[j]=C[i]+c_ij，p[j]=i。转step1。
该算法的主要计算量在于step2循环。它包括两个过程：寻找结点的过程(从S*中找到花费最小的结点i)和总花费更新的过程(更新与结点i相邻的结点的花费)。
然而，简单的Dijkstra算法无法处理时间窗约束，也无法处理负权边：在不断循环的过程中，实际上有一些边被我们忽视了，及时它的权值为负，能够优化花费，我们也不会去管。
下面我们将提出LS算法的改进版，既能处理时间窗约束，又能满足负权边。
占优剪枝：dominate在了解了解决最短路问题的LS算法后，我们再回到时间窗约束下的最短问题。因为加上了时间这一权重，我们的标记不能再像上一部分那样只记录一个变量cost。我们为每一条路径到达的每一个点时的状态分别制作一个label,为(T, C)，记录这条路径到达该点时消耗的总时间、总花费。
根据定义，我们可以给出标记的处理方法：
当然可以用穷举直接用类似Dijkstra的方法解决问题。但我们希望找出一种有效的剪枝手段以避免穷举带来的高时间复杂度。值得庆幸的是，对于寻找起点到每个点的最短路径而言，并不是所有标记都是有效的。我们通过举例来说明：
dominate rule 能让我们筛选掉无效标记。
我们可以用一个函数来直观表示这种关系：
很显然，在图中，如果两点间斜率k>=0，终点is dominated。（如X_i^1 dominateX_i^5）因为两个标记所代表的两条路径都将到达同一个点，而斜率终点的那条路径时间和cost都更高，当然更差了。而k=0时，我们在图中画了几条直线。每条直线都由一个点（代表一个标记）引出，下一个点结束。这代表，在这条直线对应的时间内，该标记的花费为最小花费。其他情况，并不能判断哪条路径更优。
我们通过一个函数EFF（）来筛选。在第一部分LS的介绍中我们提到了永久标记的概念，意思是对永久标记我们已确保其有效，在之后的拓展过程中其标记值将不再改变。我们给出拓展结点j对应的永久标记的方法。
定义：
Q_j为结点j的永久标记的集合。（Q_j中所有标记中的最小花费即为p到j的最短路径）
通过以下方式拓展Q_j：