最短路问题

最短路径是图的两个不同顶点 s , t ∈ V  之间的路径，其相对于边权重函数 c : E → R。如果图中的边都具有权重 1，则 c ( e ) = 1，对于所有边 e ∈ E ，则最短路径是 s {dISPlaystyle s} – t -在 s和 t 之间的边数最少的路径。

在文献中，该问题通常被称为最短路径问题。

复杂度很大程度上取决于权重函数的类型以及是否考虑路径或轨迹。节点和边可以在轨迹中重复，而路径不会使用节点两次。权重函数分为三种类型：

• 没有负权重的权重函数；
• 保守权重函数：如果 c ( C ) = ∑ e ∈ C c ( e ) ≥ 0 ，则称权重函数对于图 G ，是保守的_{e in C}c(e)geq 0} 对于 G的所有循环 C ;
• 具有任意权重的权重函数。

为了能够回答复杂性问题，问题的精确表述至关重要。

在没有负权重的情况下，使用 Dijkstra 算法，可以在 O ( m + n ⋅ log ⁡ ( n ) ) 的运行时间内解决问题，其中 m  表示边数，n 表示图中的顶点数。 请注意，最短路径也是最短弧。 如果所有的权重都是真正的正数，最短路径与最短遍历重合。对于任意权重和遍历，如果图形包含一个循环，其中权重之和严格为负，则存在顶点 s , t  ，它没有最短的步行路程。 如果从 s  步行到这个循环，从这个循环步行到 t ，那么可以从 s 步行到 t通过仅足够频繁地运行循环来生成。 Bellman-Ford 算法可以找到最短步行（如果存在）或通过在 O ( n m ) 运行时间内找到负循环来证明不存在。 因此，决定是否存在长度 ≤ C 的路径的问题可以在多项式时间内解决。具有任意权重和路径，这个问题的变体是 NP-hard。 这可以证明，例如，通过在最短路径问题中将所有权重设置为 -1 来减少 NP-hard 哈密顿路径问题。 请注意，此构造包含负循环，因此 NP 硬度不适用于保守的权重函数。保守的权重函数和路径 Bellman-Ford 算法可以在 O ( n m ) 中运行找到最短路径。

文献大多局限于非负权重或保守的权重函数。有了这些附加要求之一，每条最短路径自动成为最短路径，这就是为什么文献中通常没有做出这种区分的原因。

与最短路径问题相比，最长路径问题即使对于未加权的图也是 NP-hard 问题。

除了寻找最短的 s – t 路径外，还有一些其他但非常相似的问题：

此变体处理如何计算给定起始节点与图的所有其他节点之间的最短路径的问题。对于非负权重函数，Dijkstra 算法或 A* 算法可以适用于找到最短路径到图的所有节点。另一方面，对于任何保守的权重函数，Bellman-Ford 算法总是计算到所有其他节点的最短路径。

这里的目的是确定一个端节点和图中所有其他节点之间的最短路径。这个问题可以通过反转边缘方向来描述为 SSSP。

此变体是关于确定图中所有节点对之间的最短路径。 根据权重函数，依次求解每个节点的 SSSP 或使用专门的方法。

在旁边给出的图中，节点 D 和 C 之间的最短路径是从 D 开始并通过 B 到 C 去。 这里的路径成本是 9 + 8 = 17 。然而，如果你想找到一条从 D 到 E  的路径，成本为15 不是可能的最短路径，因为从 D 经 F 到 E 的路径只需要 14 = 8 + 6 有。

线性程序也可用于确定最短路径。 在这种情况下，路径被解释为在图的边缘上流量值为 1 的流量。 确定最短路径是最小成本流问题的一个特例。

如果给定图中存在 s – t 路径，则程序有可行解。但是，如果权重函数不保守，则程序是无界的。 在这种情况下，流量可以沿着一个负成本的周期任意增加。 否则问题有一个最优解 x ，它对应于一个 0 / 1 对应于条目。

事实证明，上述线性程序的对偶化具有直观的解释。

对偶程序的解 y 称为节点势。 很容易看出，对于每个解 ( y v ) v ∈ V 向量 ( y v + δ ) v ∈ V 也是一个解，其中 δ ∈ R可以任意选择。 人们通常设置 δ 的值使得 y s = 0 。然后目标函数由 max y t .

如果 P 是 s和节点 w ≠ s 之间的任意路径，那么路径的长度可以估计如下：

c ( P ) = ∑ e ∈ P c e ≥ ∑ e = ( u , v ) ∈ P y v − y u = y w

所以每个节点的潜力是路径长度的下限。 如果节点 w ≠ s 的势是最短 s – w  -路径的长度，则可以找到对偶程序的最优解到目标函数 c 集。

计算最短路径的算法通常用于计算旅行路线。 例如，可以计算两个城市之间的距离。 城市是图的节点，街道是边。

对于保守或非负目标函数，由此产生的约束最短路径问题也是 NP-hard 问题。