有向の正の重み付きグラフがあります。各エッジには使用コストがあります。私はAのお金しか持っていません。ダイクストラアルゴリズムを使用して最短経路を計算したいのですが、ルート上のエッジコストの合計はA以下でなければなりません。
最小のダイクストラ修正でこれを実行したいと思います（ダイクストラの小さな修正で実行できる場合）。できればこれをしなければなりませんO(n*log(n))が、できると思います。
誰でもこれを手伝ってくれますか？
4852 次
2 に答える
6
于 2010-04-28T05:42:49.293 に答える
0
答えは最短経路を見つけて、それがA以下の場合にそれを受け入れることと同等であるため、これを行うためにダイクストラのアルゴリズムを実際に変更する必要はありません。
もちろん、Aを超えるコストのパスにアクセスした場合は、常に内部ループを短絡する可能性があります。
編集：コストと距離を最小限に抑えたいという明確化により、必要なソリューションを明確化せずにそれを行うことはできません。あなたは最も安い道が欲しいですか？最短経路が必要ですか？コストと距離の関数が必要ですか？これらはすべて、特定のエッジに使用する必要がある重み関数を決定します。
于 2010-04-26T01:05:45.627 に答える