MedoN11's blog

Find the Shortest cycle for each vertex in a graph?
By MedoN11, history, 9 years ago, In English

Hello CodeForces!

Recently, I was participating in a gym contest, and came across a very interesting graph problem.

For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice.

The graph does not contain self loops or multiple edges.

Here it is : http://codeforces.net/problemset/gymProblem/100917/F

After the contest, I did some googling, but I can only find re-search papers discussing very complex algorithms, I'm pretty sure the author did not intend these solutions.

My solution is as follows :

Let's say edge e connect vertices u and v. Remove edge e from the graph, then re-run dijikstra from u to v. If there exists a path, then there exists a simple cycle containing both u, and v.

Repeat for each edge, and minimise over the shortest cycle for each node.

The idea really makes sense, and the problem is the time limit verdict, how can I solve this problem more efficiently?

Please keep in mind that the graph is un-directed, ( the problem becomes easier in-case it is directed )

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

answer for node i is dp[i][i], where dp[i][j] = length of shortest path between nodes i and j
You can calculate this with floyd warhsall in O(n^3).

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    This does not work for un-directed graphs when searching for a simple cycle.

    Floyd Warshall will just use each edge twice if it gives the minimum answer, thus the cycle is not simple.

    That's why I said this version is much harder ( IMO at least, I'm pretty sure someone might come up with a mind blowing approach but still :D) than directed ones.

    → Reply
»
9 years ago, # |
← Rev. 8   Vote: I like it +5 Vote: I do not like it

Maybe you'd also consider this a 'complex algorithm', but I just solved it in the following manner:

  • Fix some node u.
  • Run Dijkstra's algorithm with source u, denote the distance of a vertex v to u as dv. If you store parents, this will give you a shortest-path tree rooted at u.
  • Preprocess the tree for LCA queries.
  • Consider some edge e = {v, x} that is not in the shortest-path tree. If lca(v, x) = u, then the path is a simple cycle containing u, with weight dv + dx + w(e). The answer for vertex u is the minimum weight over all such cycles.

Code

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Awesome!

    Thanks a lot. I really appreciate that. This problem has been driving me crazy :D

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Also, instead of preprocessing for LCA queries, you can store for each node the first node you saw on the shortest path to that node other than u with a small modification to Dijkstra's, and then check if those values are different instead of checking that the LCA is u.

    → Reply