Decompose cyclic graph into minimal number of shortest path subgraphs

Given a cyclic graph, I'm looking for an algorithm that decomposes this graph into acyclic subgraphs. Each of these subgraphs would have a root vertex, where this vertex was the source from which the shortest path was computed. For example, given the cyclic graph below, where the cycle is between 3,4, and 5:

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

The shortest path subgraph with respect to 1 would be:

开发者_Go百科+---+     +---+     +---+     +---+
| 1 | --> | 3 | --> | 4 | --> | 7 |
+---+     +---+     +---+     +---+
            |
            |
            v
          +---+     +---+
          | 5 | --> | 6 |
          +---+     +---+

The shortest path subgraph with respect to 2 would be:

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

The shortest path sugraph with respect to 5 would be:

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

Notice that the shortest path subgraph with respect to 3 is a subset of 1's, 4 is a subset of 2's. 6 and 7 are leafs.

My current (naive) solution would be to perform a BFS for each node, flagging nodes as visited to prevent cycles. Then to check if the subgraphs are subsets of each other to create the minimal number of distinct subgraphs. Any ideas for a better, more formal, solution?

EDIT The graph in my situation is unweighted, but having the general solution for posterity is nice.

(Graphs made with http://bloodgate.com/graph-demo)

---

Each of the trees you've listed above is called a shortest path tree To find a single shortest path tree rooted at some vertex, you can use 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 algorithm starting at each node. Given a Fibonacci heap, this runs in O(VE + V² log V), which is very fast.

If you don't have a Fibonacci heap, or are using dense graphs, or may have negative cycles, you may want to use the Floyd-Warshall algorithm. This algorithm runs in time O(V³) and computes, for each node, the shortest path to each other node, even if there are negative edges. From here, you could recover all of the shortest path trees quite easily.

Hope this helps!

EDIT: If your graph is unweighted, then apparently there's a really good algorithm for solving this problem that runs in time O(M(n) log n), where M(n) is the time required to multiply matrices of small numbers together. Since this can be done pretty quickly (around O(n^2.3), this would be the best algorithm for solving the problem. There's a paper about the algorithm here, but it's behind a paywall. Practically speaking, unless you're dealing with really huge graphs (say, tens of thousands of nodes) I don't think that you need to worry about using this more powerful algorithm, but it's still good to know about.

---

templatetypedef, OP's use of "BFS" suggests that the graph is unweighted.

Here's an algorithm that runs in time proportional to the sum, for each root in the final collection, of the size of the subgraph reachable from that root. For, say, graphs of bounded degree, this is on the order of the size of the output.

For the sake of uniqueness I'm going to assume that "shortest path" means least in length-lex order. At a high-level, we compute an order in which to process the vertices so that if vertex u's BFS tree subsumes vertex v's, then u is ordered before v. Each vertex is processed in linear time, which includes determining the vertices it subsumes.

The order is computed by finding the strong components, topologically sorting the strong components, and then ordering the vertices within each single component arbitrarily. Clearly u subsumes v only if the set of vertices reachable from u is a proper superset of the vertices reachable from v.

To process a vertex u, compute the BFS tree from u and then determine the set of vertices whose subtrees have no arc leaving the subtree - these are the ones that get subsumed. Determine the latter by traversing the tree depth-first, recording, for each vertex v, an interval I(v) whose left endpoint is the entry time and whose right endpoint is the exit time. For each vertex v, compute the smallest interval J(v) containing I(v) and all I(w) with an arc v->w. Using DFS, compute, for each vertex v, the smallest interval K(v) containing K(w) for all descendants w of v. A vertex v other than u is subsumed if and only if K(v) = I(v).

Why should this work? We know that v's subtree of the tree rooted at u is a subset of the tree rooted at v. Suppose that u subsumes v (in other words, these two trees are equal). Then clearly the head of every arc from v's subtree goes to v's subtree, as otherwise, the head should have been explored. Conversely, suppose that u does not subsume v. The tree rooted at v contains a vertex not in v's subtree, and thus there's an arc leaving v's subtree.

I hope this description is useful to you, but I fear that your actual question involves fast point-to-point shortest path queries with subquadratic space, for which there might be better approaches.