1
$\begingroup$

I am trying to solve this problem: we have an oriented, weighted graph and we have to find a cycle with the biggest weight. Weight of a cycle is the sum of all edges forming the weight. The preferred solution is via backtracking.

My idea was to :

  1. backtrack all combinations of vertexes (0s and 1s representing whether vertex is in a subgraph)
  2. then verify if the subgraph is connected
  3. then verify if a source vertex of any edge is in the subgraph is used only once
  4. and then connecting the first vertex with the last one, thus forming a cycle.
  5. If the sum of all weights is > then max, max = sum.

However, this solution doesn't work correctly on any almost any vertex. It finds a cycle, but it never finds the biggest one. Could you help me fix my algorithm? Thanks!

$\endgroup$
1
$\begingroup$

You should note that this problem is NP-hard (i.e., when all edges have uniform weight, a cycle of maximum weight is a Hamiltonian cycle). So unless your inputs are small or somehow usefully structured, it's probably a better idea to go for heuristics since there is likely no polynomial-time algorithm.

To fix your exact algorithm, possibly with a few tricks to speed things up as well, you can have a look at the description of an algorithm given by Rubin [1].


[1] Rubin, Frank. "A search procedure for Hamilton paths and circuits." Journal of the ACM (JACM) 21.4 (1974): 576-580.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.