Undirected weighted graph. For every vertex you should find out shortest simple cycle, which includes this vertex.
I have only O(n ^ 4) solution. Can anybody help me?
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | adamant | 155 |
4 | cry | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Undirected weighted graph. For every vertex you should find out shortest simple cycle, which includes this vertex.
I have only O(n ^ 4) solution. Can anybody help me?
Name |
---|
Auto comment: topic has been translated by Domonion (original revision, translated revision, compare)
are there negative edges?
seems like it's not. since it will make this problem NP-hard.
If O(n^3logn) is good enough, for each node, for each edge of the node, remove the edge, run dijkstras to find the distance from the node to the neighbor on the other side of the edge, and add the edge weight to it. The answer is the minimum of these.
Dijkstra's Algorithm does not run in O(N log(N)) time.
I think it's possible to do in
. To compute answer for vertex v, run Dijkstra from it then for every edge w suposse that this edge is included in some cycle of v in the way
(where wA and wB are vertexes connected by edge w) and calculate its weight. Answer for v gonna be a minimum of these weights.
It's also O(n^3 log n)
No it's not. For each vertex you run dijkstra and check all edges so actually it is O(n * (m + mlogn)). Of course if there will be like n2 edges then it indeed gonna work in O(n3 * logn), but if such constraints exists then n should be quite small.
Your algorithm does not always compute simple cycles. Consider the cycle
, which is not a simple cycle, but is taken into account by your algorithm.
please ignore this :(
Won't work, the graph is undirected, so A[v][v] will be 2x the lightest outgoing edge from v.
omg i was stupid. Sorry for that
I don't know if this is a coincidence or not, but it seems you are not the only one solving this problem: http://research.haifa.ac.il/~raphy/papers/all-cycles.pdf