在称重的单位图中找到最短的路径

Question

据说有向图是 单一 如果对于图表$ g =（v，e）$中的任何两个顶点$ u $和$ v $，则最多只有一条简单的路径从$ u $到$ v $。

假设我得到了一个单膜图$ g $，以便每个边缘的重量为正或负重，但没有负重周期。

由此我想找到一个$ O（| V |）$算法，该算法从源节点$ s $中找到所有节点的最短路径。

我不确定如何解决这个问题。我试图看看我如何使用它不包含负重周期的事实，当然，最多只能在任何节点$ u $到$ v $之间进行一条简单的路径。

Answer 1

选择数据表示

首先，查看结果的大小。您希望收集最短路径从$ s $到其他节点。除非路径的平均长度是由常数界的（否则：任何列表都是unipath，如果您将$ s $ root的总路径的总长度为$ n（n-1）/2 $ n $是列表的长度），您需要在数据表示中谨慎：包含路径的结构需要在路径之间使用共享。

不包括周期，从$ s $到任何其他节点$ u $都有一条路径。如果该路径通过中间节点$ t $，则该路径的第一部分是从$ s $到$ t $的所需路径。

我建议将结果存储在一个数组中，由从$ 0 $到$ | e | -1 $的节点索引，$ s = 0 $。阵列中的每个元素都在该节点的路径上存储上一个节点的索引（使用EG $ -1 $作为$ S $无法到达的节点的特殊标记）。从$ s $到$ t $的路径将为$（s = r [ ldots r [t] ldots]， ldots，r [r [t]]，r [t]，t），t）$。

遍历图

将$ r $初始化为所有$ -1 $。

从$ s $开始，执行图形的深度优先或广度遍历。每次达到节点$ u $时，都会将$ r [u] $设置为其前身。

由于有周期，因此可能会多次达到一个节点。拥有$ r [u] ne -1 $表示已经访问了$ u $。

证明正确性

由于具有单一属性的属性，只要我们尚未完成周期，我们如何达到每个节点都无关紧要。只有一条简单的路径。

证明复杂性

该算法可能多次达到每个节点，因此尚不清楚其复杂性为$ O（| V |）$。实际上，完成的工作实际上是$ theta（| e_0 |）$，其中$ v_0 $是可从源可到达的边缘。更确切地说，我们仅在一种情况下仅一次到达节点：如果节点是我们在特定周期中达到的第一个节点，在这种情况下，我们达到了两次（一次是从简单的路径到完成的，并且在完成周期后一次）。

好吧。让我们证明，在一个单位图中，基本周期的数量最多可以与节点数量线性增长。 （基本周期是一个不包含较短周期的周期。）在以下讨论中，我假设该图没有自我边缘（从节点到自身的边缘都没有边缘；无论如何，这种边缘与路径构造无关紧要）。

单位图可以具有循环，但以非常约束的方式。如果我们可以以某种方式将每个循环与一个不同的节点相关联（或至少，每个节点数量最多有界数），那将是很好的。周期可以共享节点吗？不幸的是，是的。

您可以有$ m $ $循环共享一个节点$ a $，而没有其他节点。所得图是单膜片。对于长度2的循环，这是一个带有中央节点$ a $和任何数量的节点$ b_i $的星形图案，因此$ forall i，a leftrightArows b_i $。

因此，我们需要更加努力。好吧，让我们尝试以归纳来证明它。令$ ＃v（g）$是图$ g $，$ ＃e（g）$边缘数和$ ＃c（g）$的节点数量的数量t自边。我断言，如果$ g $是单一的，而不是空的，则$ ＃c（g） le #v（g）-1 $。

对于具有一个或两个节点的图形，这很明显。假设对所有图的断言都保留，从而使$ ＃v（g）<n $，让$ g $是带有$ n $ nodes的单体图。如果$ g $没有周期，则$ 0 = #c（g）< #v（g）$，案例关闭。否则，令$（a_1， ldots，a_m）$为基本周期。

折叠周期：让$ g'$是其节点的图表，其节点为$ g $ schous $ {a_1， ldots，a_m } $加上节点$ a $ and a $ and a $ a $ and的边缘为$ g $不涉及$ a_i $'s，加上$ a rightArrow_ {g'} b $，每当$ c everists i，a_i rightarrow_g b $和$ b rightArrow_ {g'} a $时rightarrow_g a_i $。 $ g'$中的每条路径诱导$ g $中的路径（如果路径涉及$ b rightarrow a rightarrow c $，然后由$ b rightarrow a_i rightarrow a_ rightarrow a_ {i+1} rightarrow rightarrow ldots替换。 rightarrow a_j rightarrow c $ in $ g $）。因此，$ g'$是单一的。此外，由于$ g $中的循环不共享边缘，因此$ g'$在$ g $中具有所有周期，除了我们消除的一个：$ ＃c（g'）= #c（g）-1 $ 。通过归纳，$ ＃c（g'） le #v（g'） - 1 $。由于$ ＃v（g'）= #v（g） - m + 1 $，我们有$ ＃c（g）= #c（g'） + 1 le le #v（g） - m = nm le n-1 $。

这是证明的结论。遍历最多$ 2 | V | -2 $边缘。