帯域幅可用性のためのアルゴリズム設計

Question

私はN個のノードのグラフを持っています。私はすべてのリンクの帯域幅消費量を持っています。ノードsからノードtまでのパスで利用可能な帯域幅が最も小さいリンクをパスのボトルネックと呼びます。ノードsとノードtとの間の帯域幅利用可能性を見つけるために、DFSを実行して2つのノード間にN個のパスを見つけて、各パスのボトルネックを見つけています。私は平均ボトルネックを見つけるためにこれらのボトルネックの平均をとっています。これを単一の数字として使用して、ノードとノードtの間の帯域幅の可用性を表すことはできますか？長所と短所は何ですか？これが適切な場所でないかどうか尋ねる正しい場所を教えてください。

それはあなたが探しているもののように聞こえる

Answer 1

は、ネットワークフロー分析であり、特にMax flow, Min Cut.

あなたの現在の実装では、一度に複数の経路に沿ってデータを送信することができるかもしれないという事実を無視しています。

最後に、Djikstraのアルゴリズムを使用して、最大のボトルネックを持つパスを見つけることができます。