1

I want to find shortest cycle made of exactly 4 edges in weighted directed graph (shortest = minimum sum of weights of edges).

I know that I could use Floyd–Warshall algorithm for finding shortest cycle in graph as is described here. But I don't know how to find shortest cycle made of exactly four edges.

Community
  • 1
  • 1
Superian007
  • 395
  • 7
  • 25

1 Answers1

3

Since you mention Floyd-Warshall, I think having an adjacency matrix is not a problem.

Let us look at it this way: a cycle of length 4 has the form a->b->c->d->a. Split that into two pairs of two edges: a->b->c and c->d->a.

Given the adjacency matrix, we can easily compute the matrix of shortest paths using exactly two edges: the shortest path from x to z is the minimum of x->y->z for every vertex y. The vertex y giving that minimum can be stored as well if we need to present the cycle, not only its length.

Now, to find the shortest cycle of length 4, just iterate over all possible pairs (a, c). For each such pair, we have the minimum cost of traveling from a to c by exactly two edges and the minimum cost of traveling from c to a by exactly two edges. The pair with the minimum sum of these two costs gives us the desired cycle.

The solution runs in O(n^3) with O(n^2) additional memory.

Gassa
  • 8,546
  • 3
  • 29
  • 49
  • Can you please describe more why time complexity is `O(n^3)`? – Superian007 Apr 12 '15 at 09:01
  • 1
    @Superian007 The n^3 part is `for x, for z, d2[x][z] = min (for y) d[x][y] + d[y][z]`. Here, `d` is the adjacency matrix, and `d2` is the costs of traveling by exactly two edges. – Gassa Apr 12 '15 at 09:04
  • Shouldn't we first find all vertices `y` that are between two vertices `x` and `z`? Because how do we know that if we choose vertex `x` there will be path to vertex `z`? – Superian007 Apr 12 '15 at 09:18
  • @Superian007 In an [adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix), `d[x][y]` is the length of the edge from `x` to `y` (one edge, not any path), or infinity if there is no such edge. Now, in our new matrix, `d2[x][z]` is the length of the shortest path of exactly two edges between `x` and `y`, or infinity if there is no such path. Instead of searching for some `y`, we iterate over all possible vertices `y` to find the minimum. If some, or both, edges `d[x][y]` and `d[y][z]` are not present, the result for `d[x][y] + d[y][z]` will be infinity. – Gassa Apr 12 '15 at 10:12
  • _Now, in our new matrix, `d2[x][z]` is the length of the shortest path of exactly two edges between `x` and `y`_ Just to be sure, shouldn't there be: _path of exactly two edges between `x` and `z`_? – Superian007 Apr 12 '15 at 10:57