CODEWITHSUNDEEP
algorithmgraphgraph-theory
Superian007
Superian007

Reputation: 395

Finding shortest 4-edge cycle in graph

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.

Upvotes: 1

Views: 395

Answers (1)

Gassa
Gassa

Reputation: 8844

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.

Upvotes: 3

Related Questions