将循环图分解为最少数量的最短路径子图

Question

给定一个循环图，我正在寻找一种算法将该图分解为非循环子图。每个子图都有一个根顶点，该顶点是计算最短路径的源。例如，给定下面的循环图，其中循环在 3,4 和 5 之间：

                      +-------------------------+
                       |                         |
                       |                         |
            +----------+----------+              |
            v          |          v              |
+---+     +---+      +---+      +---+     +---+  |
| 1 | --> | 3 | <--> | 4 | <--> | 5 | --> | 6 |  |
+---+     +---+      +---+      +---+     +---+  |
                       ^                         |
                       |                         |
                       |                         |
                     +---+                       |
                     | 2 |                       |
                     +---+                       |
                     +---+                       |
                     | 7 | <---------------------+
                     +---+

相对于 1 的最短路径子图将是：

+---+     +---+     +---+     +---+
| 1 | --> | 3 | --> | 4 | --> | 7 |
+---+     +---+     +---+     +---+
            |
            |
            v
          +---+     +---+
          | 5 | --> | 6 |
          +---+     +---+

相对于 2 的最短路径子图将是：

          +---+
          | 7 |
          +---+
            ^
            |
            |
+---+     +---+     +---+     +---+
| 2 | --> | 4 | --> | 5 | --> | 6 |
+---+     +---+     +---+     +---+
            |
            |
            v
          +---+
          | 3 |
          +---+

相对于 2 的最短路径 su 图5 将是：

+---+     +---+     +---+     +---+
| 6 | <-- | 5 | --> | 4 | --> | 7 |
+---+     +---+     +---+     +---+
            |
            |
            v
          +---+
          | 3 |
          +---+

请注意，关于 3 的最短路径子图是 1 的子集，4 是 2 的子集。 6和7是叶子。

我当前（天真的）解决方案是对每个节点执行 BFS，将节点标记为已访问以防止循环。然后检查子图是否是彼此的子集，以创建最小数量的不同子图。对于更好、更正式的解决方案有什么想法吗？

编辑 在我的情况下，图表是未加权的，但是为后代提供通用的解决方案是很好的。

（使用 http://bloodgate.com/graph-demo 制作的图表）

Answer 1

上面列出的每棵树都称为最短路径树 要查找以某个顶点为根的单个最短路径树，您可以使用 Dijkstra 算法，该算法既查找从源节点到每个其他节点的最短路径，又显示使用哪些边到达这些节点。假设该图不包含任何负边，这会立即为您提供单个节点的最短路径树。如果您想列出所有树，可以通过从每个节点开始运行 Dijkstra 算法来实现。给定斐波那契堆，其运行时间为 O(VE + V² log V)，速度非常快。

如果您没有斐波那契堆，或者正在使用密集图，或者可能有负循环，您可能需要使用 Floyd-Warshall 算法。该算法运行时间为 O(V³)，并为每个节点计算到每个其他节点的最短路径，即使存在负边也是如此。从这里，您可以很容易地恢复所有最短路径树。

希望这有帮助！

编辑：如果你的图没有加权，那么显然有一个非常好的算法可以解决这个问题，运行时间为 O(M(n) log n)，其中 M(n) 是将小数字的矩阵相乘。由于这可以很快完成（大约 O(n^2.3），因此这将是解决该问题的最佳算法。有一篇关于该算法的论文此处，但它位于付费墙后面。实际上，除非你正在处理非常巨大的图表（例如，数以万计的节点），我认为你不需要担心使用这种更强大的算法，但了解它仍然是件好事。

Answer 2

templatetypedef，OP 使用“BFS”表明该图是未加权的。

这是一个算法，其运行时间与最终集合中每个根的可从该根到达的子图的大小之和成正比。例如，对于有界度图，这与输出的大小有关。

为了唯一性，我假设“最短路径”意味着长度-词法顺序最少。在高层次上，我们计算处理顶点的顺序，以便如果顶点 u 的 BFS 树包含顶点 v 的 BFS 树，则 u 的顺序排在 v 之前。每个顶点都在线性时间内处理，其中包括确定它包含的顶点。

通过查找强分量、对强分量进行拓扑排序、然后对每个单个分量内的顶点进行任意排序来计算顺序。显然，只有当从 u 可达的顶点集是从 v 可达的顶点的真超集时，u 才包含 v。

要处理顶点 u，请根据 u 计算 BFS 树，然后确定其子树没有离开 v 的弧的顶点集。子树 - 这些是被包含的子树。通过深度优先遍历树来确定后者，为每个顶点 v 记录一个区间 I(v)，其左端点为进入时间，右端点为退出时间。对于每个顶点 v，计算包含 I(v) 和所有 I(w) 且弧 v->w 的最小区间 J(v)。使用 DFS，对于每个顶点 v，计算包含 v 的所有后代 w 的 K(w) 的最小区间 K(v)。当且仅当 K(v) = I(v) 时，包含除 u 之外的顶点 v 。

为什么这会起作用？我们知道，以u为根的树的v的子树是以v为根的树的子集。假设u包含v（换句话说，这两棵树是相等的）。然后显然，从 v 的子树开始的每个弧的头部都会到达 v 的子树，否则，头部应该已经被探索过。相反，假设u不包含v。以v为根的树包含不在v的子树中的顶点，因此有一条弧离开v的子树。

我希望这个描述对您有用，但我担心您的实际问题涉及二次空间的快速点对点最短路径查询，对此可能有更好的方法。