这是NP-hard问题。
决定所有汽车是否能在最多给定的k个时间单位内完成其行程的问题是NP-hard问题，即使在以下任何组合的同时限制下也是如此：所有汽车以单位速度行驶，每条边的长度为1，k=3。 NP-hard问题意味着几乎肯定没有多项式时间算法可以解决每个实例。为了证明这一点，我将从NP-hard问题3SAT中给出一个约简：在这个问题中，我们得到一个布尔表达式，它是n个子句的连接（AND），每个子句都是3个文字的析取（OR），每个文字都是变量或其否定（NOT）。总共有m个变量，每个变量可以分配为TRUE或FALSE；我们的任务是确定整个表达式是否可满足-即是否存在任何分配TRUE或FALSE值的m个变量，使整个表达式为TRUE。
从任意3SAT实例构造您问题的实例
假设我们有一个具有n个子句和m个变量的3SAT实例。我们可以构建一个您问题的实例，其中每个变量成为一条边，沿着该边的交通方向（从左到右或从右到左）对应于变量的值（TRUE或FALSE）。每个子句都成为一个连接到这些变量边的3个端点的小装置。直观地说，每个子句装置为从其起点开始的车辆提供了3种选项，以到达其相应的终点。具体来说：
- 首先，删除包含变量和其否定作为文字的子句。这样可以从图形中删除长度为2的行程，而不影响原始表达式的可满足性，因为这样的子句可以通过任何分配来满足。
- 对于每个变量x_i，创建两个顶点u_i和v_i，以及边缘（u_i，v_i）。此构建中的所有边缘均具有重量（距离？）1。
- 对于所有1 <= j <= n，按以下方式构建与第j个子句对应的小装置：创建一个顶点s_j和一个顶点t_j。让第j个子句中的文字为a、b和c。令文字a中的变量为x_i。如果a是正文字，则创建边缘（s_j，u_i）和（v_i，t_j），否则（即如果它等于“NOT x_i”），则创建边缘（s_j，v_i）和（u_i，t_j）。对于文字b和c也同理。
- 最后，为每个1 <= j <= n的（源，目标）对添加（s_j，t_j）。给每个这样的汽车单位速度。
我现在宣称，如果原始的3SAT实例可满足，那么你问题的新构造实例只要有一个持续时间不超过3的解决方案，就可以满足。
YES to 3SAT instance => YES to instance of your problem
首先我将证明，如果3SAT实例可满足，则存在一个解决方案，使得您问题的新构造实例持续时间为3。在这种情况下，我们可以假设存在一个令人满意的赋值Y，因此对于每个1 <= i <= m，让y_i是一些这样的令人满意的赋值中变量x_i的分配。现在，在刚刚构造的实例中，将与s_j相邻的每条边朝向远离s_j，将与t_j相邻的每条边朝向t_j，并且每个变量边缘如下：如果y_i = TRUE，则从u_i到v_i定向边(u_i, v_i)，而另一方面，如果y_i = FALSE，则从v_i到u_i定向边。由于根据假设Y是一个令人满意的赋值，我们知道每个子句都至少包含一个求值为TRUE的文字：也就是说，在每个子句中，至少有一个包含变量x_i的文字z，其中z是正的且x_i = TRUE，或者z是负的且x_i = FALSE。这意味着，对于每个子句j，至少有一条从s_j到t_j的路径与上述边缘定向一致。显然，如果汽车只在方向与上述定向相同的边上行驶，就永远不会有两辆汽车以相反方向穿过一条边，因此这样的汽车行程不会互相干扰。由于这些从s_j到t_j的路径都具有长度3且没有旅行互相干扰，因此所有旅行可以在3个时间步骤内同时完成。
YES to instance of your problem => YES to 3SAT instance
现在我将展示，如果你的问题的解决方案持续时间最多为3，则存在满足原始3SAT实例的赋值。假设存在这样的解决方案：那么显然，每次旅行必须在最多3个时间单位内完成。为了让汽车从s_j到t_j，它必须使用至少与s_j相邻的3条边之一，并且至少使用与t_j相邻的3条边之一，因此它必须花费至少2个时间单位；此外，由于我们删除了任何包含变量及其否定的子句，所以对于任何j，没有任何一个顶点与s_j和t_j都相邻，因此需要至少一个更多的边，这意味着我们希望的最短路径为3个时间单位（因为每条边需要1个时间单位）。因此，解决方案中的每次旅行必须花费恰好3个时间单位，沿着不会因来自另一侧的车辆而出现阻塞的3条边路径。请注意，这种路径上的中间段必须是单个变量边，因为从某个u_i到v_i或反之亦然的唯一其他方法涉及通过至少2个以上的边“折回”。特别地，对于从s_j开始的旅行，它必须是与第j个子句中的3个文字对应的3个不同变量边之一。具体而言，假设第j个子句中的文字为a、b和c。令x_i为文字a中的变量。如果a为正，则“从u_i到v_i”是从s_j开始的旅行中允许的3个路径之一，否则（即如果a为负），“从v_i到u_i”是。剩下的文字b和c也是如此。因此，到目前为止，我们已经建立了以下事实：
- 对于每个1 ≤ j ≤ n，汽车可以使用与第j个子句中的文字对应的3个中间段之一，在最多3个时间单位内从s_j到t_j旅行。
我们按照以下方式构建3SAT实例的解决方案：对于每个变量x_i，如果边（u_i，v_i）被一辆或多辆汽车从u_i到v_i穿过，则将TRUE分配给y_i；如果它被一辆或多辆汽车从v_i到u_i穿过，则将FALSE分配给y_i；否则（如果根本没有穿过边），任意分配任何值给y_i。我们需要证明两件事情：没有变量被分配为TRUE和FALSE，且该赋值导致表达式的值为TRUE。
首先，根据上述规则，变量 x_i 能被赋值为 TRUE 和 FALSE 的唯一条件是每个方向上至少有一辆车穿过边 (u_i, v_i)。假设这是真的：某个变量-边 (u_i, v_i) 在解决方案中被两个不同的汽车旅行以相反的方向穿过。那么显然，这两辆车中至少有一辆必须暂停至少 1 个时间步骤，让另一辆通过这条边。但是，解决方案将需要至少 4 个时间步骤，这与我们假设的持续时间最多为 3 个时间步骤的解决方案相矛盾，因此如果任何车辆穿过边 (u_i, v_i)，那么它们都是在同一个方向上这样做的，因此每个变量最多被分配为 TRUE 或 FALSE。
其次，对于每个 1 <= j <= n，我们可以将第 j 个 3SAT 实例的子句重新解释为“一辆车可以使用与子句 j 中文字对应的中间段之一，在最多 3 个时间单位内从 s_j 到达 t_j”，其中“对应”与之前使用的意义相同。请注意，在此解释下，3SAT 实例等价于上面已经确定为 TRUE 的语句，并且仍然与原始的 3SAT 问题形式上等价（因为我们所做的只是给它的变量和子句一个解释）。
由此可知，我们刚刚从您问题的实例的解决方案中构建的 3SAT 问题的变量赋值是没有矛盾的，并且产生了 TRUE 值：即，3SAT 公式是可满足的。
总之，我们现在已经确定了对于问题“是否存在此 3SAT 表达式的满足分配？”的 YES 答案意味着“是否存在一种方法，在 3 个时间步骤或更短的时间内让所有汽车从起点到达目的地？”的 YES 答案，反之亦然。因此，任何一个问题的 NO 答案也意味着另一个问题的 NO 答案：也就是说，这些问题是等价的。我们从给定的 3SAT 实例中以多项式时间构建了您问题的实例，因此如果有某种算法可以在多项式时间内解决您的问题，则可以使用该算法来解决任何 3SAT 实例 - 首先构造这样一个问题的实例，调用该算法来解决该实例作为子程序，然后返回答案。因此，您的问题至少与 3SAT 一样难，即 NP-hard。
