重み付きグラフ（有向または無向）が与えられた場合、最大の重みを持つグラフのサイクルを見つける必要があります。
サイクルの重みは、グラフのエッジの重みの合計です。
それは、私たちができる基本サイクルだけでなく、任意のサイクルにすることができます
グラフのすべてのサイクルを列挙してから最大値を計算することもできますが、サイクルの総数は非常に大きくなる可能性があります（グラフが完成している場合、最初と最後の頂点が同一である頂点のシーケンスはサイクルです）。
すべてのサイクルを列挙せずに、その最大ウェイトサイクルを見つけるアイデアはありますか？
グラフ上で仮説が必要な場合（たとえば、正の重み）、それらを示してください。
これはNP困難です。
ハミルトン閉路問題はこれに還元することができます。
ハミルトン閉路が存在するかどうかを確認する必要があるグラフを前提として、各エッジに重み1を割り当てます。
次に、アルゴリズムを実行して最大のウェイトサイクルを取得します。重みが<nの場合、元のグラフにはハミルトン閉路がありません。それ以外の場合は、ハミルトン閉路があります。
特定のケースで最小の重み付きパスを見つけることができる場合は、すべての重みの符号を逆にして、アルゴリズムを適用してください。もちろん、モロンの議論は正しいので（しゃれは意図されていません）、あなたはいくつかの述べられていない仮定をしています。あなたがしている仮定は、正の重みであるか、負の重みサイクルがない可能性があります。考えられる仮定の無限の空間で人々を検索させるのではなく、それらを述べる努力をするべきだと思います。硬度の結果に関しては、これもいくつかの方法で概算するのは難しいです、この論文をチェックしてください。同じ論文には、重要なタイプのグラフについていくつかの肯定的な結果が含まれていますが、重み付けされていない最長のパスに関係しているため、論文のほとんどのアルゴリズムはあなたの場合には直接役立たないと思います。「ヘビーサイクル」を検索すると、興味深い論文がたくさん見つかりますが、それらはより数学的な性質を持っています。重みが小さい整数（グラフのサイズの多項式まで）の場合は、すべてのエッジを重みのないパスに置き換えて、問題を重みのない場合に減らすことができます。これがある程度役立つことを願っていますが、あなたはあなたの手に未解決の研究問題を抱えているかもしれません。