Introduction

Finding a maximum-weight cycle sounds straightforward, but the right answer depends heavily on the graph class. In a general weighted graph, finding the maximum-weight simple cycle is a hard combinatorial problem, so there is no simple Dijkstra-style algorithm that solves it efficiently for all inputs.

The First Important Distinction

You must clarify whether you mean:

• any cycle, possibly repeating vertices or edges
• a simple cycle, where vertices are not repeated except for the start and end

For most algorithm discussions, people mean a simple cycle. In a general graph, the maximum-weight simple cycle problem is NP-hard, which means an exact efficient algorithm for all graphs is not expected.

That is why claims about a generic greedy or shortest-path-style solution are usually misleading.

What You Can Do for Small Graphs

For small graphs, a practical exact method is depth-first search with backtracking, keeping track of the best cycle found.

1def max_weight_cycle(graph):
2    best_weight = float("-inf")
3    best_cycle = None
4
5    def dfs(start, current, visited, path, weight):
6        nonlocal best_weight, best_cycle
7
8        for neighbor, edge_weight in graph[current]:
9            if neighbor == start and len(path) >= 2:
10                total = weight + edge_weight
11                if total > best_weight:
12                    best_weight = total
13                    best_cycle = path + [start]
14            elif neighbor not in visited:
15                visited.add(neighbor)
16                dfs(start, neighbor, visited, path + [neighbor], weight + edge_weight)
17                visited.remove(neighbor)
18
19    for node in graph:
20        dfs(node, node, {node}, [node], 0)
21
22    return best_weight, best_cycle
23
24
25graph = {
26    "A": [("B", 3), ("C", 2)],
27    "B": [("C", 4), ("A", 1)],
28    "C": [("A", 5)],
29}
30
31print(max_weight_cycle(graph))

This is exact, but it does not scale well. That is the tradeoff.

Why the General Problem Is Hard

If you could solve the maximum-weight simple cycle problem efficiently in a completely general graph, you could also solve hard cycle-selection problems by choosing weights cleverly. That is why the difficulty is not accidental.

So the practical question becomes: what special structure does your graph have?

For example:

• in a DAG, there are no cycles at all
• in very small graphs, exhaustive search is fine
• in special graph families, dynamic programming or combinatorial shortcuts may exist
• in large general graphs, heuristics or approximations may be the only realistic option

Directed Versus Undirected Graphs

Directed and undirected graphs behave differently. In a directed graph, edge direction constrains which cycles are even possible. In an undirected graph, every undirected cycle can be traversed in two directions, which affects how you count duplicates when searching.

That matters in brute-force or backtracking implementations. Without careful duplicate handling, the same cycle may be rediscovered many times.

Practical Strategies

If the graph is small, use exact backtracking.

If the graph is large but sparse, first decompose it into strongly connected components in the directed case or biconnected components in the undirected case. There is no point searching for cycles in parts of the graph where cycles cannot exist.

If the graph is large and the problem is genuinely general, consider whether you really need the exact maximum-weight cycle or whether a good high-weight cycle found by heuristic search is sufficient.

Common Pitfalls

The biggest pitfall is assuming the problem has a simple polynomial-time exact solution for all weighted graphs. In general, it does not.

Another issue is not defining what counts as a valid cycle. Allowing repeated vertices versus requiring a simple cycle changes the problem substantially.

Developers also sometimes forget duplicate counting in brute-force search and mistakenly think they found several distinct best cycles when they actually found the same cycle in different rotations.

Finally, if edge weights can be negative, zero, or mixed, intuition about "just keep adding good edges" becomes unreliable. Local decisions do not guarantee a globally optimal cycle.

Summary

• The maximum-weight simple cycle problem is hard in general graphs.
• Exact backtracking works for small graphs but does not scale well.
• Problem details such as directed versus undirected and simple versus non-simple cycles matter a lot.
• Decompose the graph and exploit special structure whenever possible.
• For large general graphs, heuristics may be more realistic than exact search.