首页 文章

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

提问于
浏览 次
3

给定一个循环图，我正在寻找一种算法，将该图分解为非循环子图 . 这些子图中的每一个都具有根顶点，其中该顶点是计算最短路径的源 . 例如，给定下面的循环图，其中循环在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的最短路径是：

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

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

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

EDIT 我的情况中的图表没有加权，但为子孙后代提供一般解决方案很好 .

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

algorithm graph shortest-path

2 回答

  • 3

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

    这是一个算法，它按时间与最终集合中每个根的总和成比例，从该根可以到达的子图的大小 . 例如，对于有界度的图，这是输出大小的顺序 .

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

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

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

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

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

    回复于
  • 2

    您在上面列出的每个树都称为 shortest path tree 要查找以某个顶点为根的单个最短路径树，您可以从每个节点开始使用Dijkstra 's algorithm, which both finds shortest paths from a source node to every other node and shows which edges are used to arrive at those nodes. This immediately gives you the shortest path tree for a single node, assuming that the graph does not contain any negative edges. If you wanted to list all the trees, you could do so by running Dijkstra' s算法 . 给定Fibonacci堆，它在O（VE V2 log V）中运行，这非常快 .

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

    希望这可以帮助！

    EDIT ：如果你的图是未加权的，那么显然有一个非常好的算法来解决这个问题，它在时间O（M（n）log n）中运行，其中M（n）是将小数矩阵相乘所需的时间 . 由于这可以很快完成（在O（n2.3）附近，这将是解决问题的最佳算法 . 有一篇关于算法 here 的文章，但是's behind a paywall. Practically speaking, unless you'正在处理真正巨大的图形（例如，数十个）成千上万的节点）我还不太了解 .

    回复于

相关问题