有向加重グラフ (正の整数の加重) を取り、(総加重ではなく) 最小の平均加重を持つグラフ内のサイクルを見つけるアルゴリズムを探しています。
同様の質問に基づいて (ただし総重量について)、Floyd-Warshall アルゴリズムの修正を適用することを検討しましたが、次のプロパティに依存することになり、これは成立しません(これを示す反例を提供してくれた Ron Teller に感謝します)。 「頂点 U、V、W について、U から V へのパス p1、p2 と、V から W へのパス p3、p4 がある場合、U から W に到達するこれらのパスの最適な組み合わせは、p1 よりも優れています。 p2 の後に p3、p4 の良い方が続きます。」
このプロパティに依存しない他のどのアルゴリズムを検討できますか?
編集: もはや関係のない次の段落を質問の下に移動しました。
このプロパティは直感的に見えますが、同じように望ましい 2 つのパスの場合には当てはまらないようです。たとえば、p1 の総重量が 2 で長さが 2 で、p2 の総重量が 3 で長さが 3 の場合、どちらも優れているとは言えません。ただし、p3 と p4 の合計重量が長さよりも大きい場合は、p2 が p1 よりも優先されます。私の希望するアプリケーションでは、各エッジの重みは正の整数であるため、このプロパティが適用され、引き分けの場合はパスが長いほど良いと想定できると思います。ただし、これが機能することをまだ証明できないため、これに依存するアルゴリズムの正確性を検証することはできません。