将循环图分解为最短路径子图的最小数目

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 | 
      +---+ 

相对于最短路径sugraph至5将是：

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

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

我目前的（天真的）解决方案将是为每个节点执行一个BFS，标记节点访问以防止周期。然后检查子图是否是彼此的子集以创建最小数量的不同子图。任何更好，更正式的解决方案的想法？

编辑在我的情况图是不加权的，但有后人的一般解决方案是很好的。

（与http://bloodgate.com/graph-demo由图）

Answer 1

templatetypedef，OP使用“BFS”表示该图未加权。

下面是一个算法，该算法的运行时间与最终集合中每个根的总和成正比，该总和可以从该根可访问的子图的大小。例如，对于有界度数的图，这与输出大小的顺序有关。

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

通过查找强组分，拓扑排序强组分，然后任意排序每个单一组分中的顶点来计算顺序。显然，只有从u到达的顶点集合是从v到达的顶点的适当超集，u才包含v。

要处理顶点u，从u计算BFS树，然后确定子树具有的顶点集没有电弧离开子树 - 这些是包容的。通过遍历树深度优先来确定后者，为每个顶点v记录其左端点是输入时间并且其右端点是退出时间的间隔I（v）。对于每个顶点v，用弧v-> w计算包含I（v）和I（w）的最小间隔J（v）。使用DFS，为每个顶点v计算v的所有后代w的包含K（w）的最小间隔K（v）。当且仅当K（v）= I（v） 。

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

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

Answer 2

每次你上面列出的被称为shortest path tree要找到一些顶点为根的单一最短路径树，你可以使用Dijkstra算法的树木，这两者的发现从源节点到每个其他节点的最短路径，并显示使用哪条边到达这些节点。这会立即为您提供单个节点的最短路径树，假定该图不包含任何负边。如果你想列出所有的树，你可以通过从每个节点开始运行Dijkstra算法来实现。给定一个斐波那契堆，它运行在O（VE + V log V），它非常快。

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

希望这会有所帮助！ （M（n）log n），其中M（n）是乘法所需的时间小数字矩阵在一起。由于这可以很快地完成（大约O（n ^2.3），这将是解决问题的最佳算法。有一篇关于算法here的文章，但它位于付费墙之后，实际上，处理真正巨大的图（比方说，数以万计的节点）我不认为你需要担心使用这个更强大的算法，但它仍然是很好的了解。