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 :
- backtrack all combinations of vertexes (0s and 1s representing whether vertex is in a subgraph)
- then verify if the subgraph is connected
- then verify if a source vertex of any edge is in the subgraph is used only once
- and then connecting the first vertex with the last one, thus forming a cycle.
- 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!