加重グラフと、このリンクで問題解決しようとするすべてのペアのパス

Question

アム：

https://www.chegg.com/homework-help/questions-and-answers/consider-weighted-directed-graph-g-n-vertices-e-edges-weights-integers-suppose-g-contains--q12054851

を（これは宿題の問題ではありません）

nの重み付き有向グラフGを考えてみましょう頂点とeエッジ、およびウェイトは整数です。 Gが負のサイクルを含まず、Gの頂点uとvのすべての対に対して、uからvまでの距離は、いくつかの正の整数dについて[-2d、2d]の範囲に入ると仮定する。 Gで特定のエッジ（x、y）を固定し、そのエッジに関連付けられたウェイトを変更してGの距離に何が起こるかを検討します（他のエッジウェイトはすべて固定したままにします）。

Gを入力として、Gの指定されたエッジ（x、y）を取るアルゴリズムを設計します。アルゴリズムの出力は、このエッジ（x、y）の重みが、 Gのすべての距離が同じになるようにすることができます。この範囲は、エッジ（x、y）の元の重みを含まなければならないので、空ではないことに注意してください。また、範囲の終点として無限大が発生する可能性があります（範囲が有限でない可能性があります）。このため、エンドポイントとして「∞」を返すことがあります。あなたのアルゴリズムの実行時間は、n、e、およびdの多項式でなければなりません（実行時間はこれらのパラメータのいずれも指数として現れないようにしてください）。アルゴリズムが正しい理由を証明してください。

私は以下の行について考えています： 距離が範囲内にあるので、重みも範囲内でなければなりません。 1つの選択肢は、Djkstraを複数回実行することです。これをどのように最適化するのですか？

Answer 1

はい、Dijkstraをn回実行できます。あるいは、これらの問題を解決するために設計されたFloyd-Warshallを実行することもできます。全体として、それらは同様の複雑さの境界を有する。