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

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

关于 5 的最短路径 sugraph 是:

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

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

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

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

(用 http://bloodgate.com/graph-demo 制作的图表)

Answer 1

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

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

希望这对您有所帮助!

编辑:如果您的图表未加权，那么显然有一个非常好的算法可以解决这个问题，运行时间为 O(M(n) log n)，其中 M(n) 是将小数矩阵相乘所需的时间。由于这可以很快完成(大约 O(n^2.3)，这将是解决问题的最佳算法。有一篇关于该算法的论文 here ，但它在付费墙后面。实际上，除非你处理的是非常大的图(比如，数万个节点)，否则我认为你不需要担心使用这种更强大的算法，但它仍然很高兴知道关于。