重み関数と頂点 s を持つ有向グラフが与えられます。私の目標は、他の頂点 v について、s から v までの最短経路で、ちょうど 1 つの負のエッジを通過するものを見つけることです。アルゴリズムの時間計算量は O(|E| + |V|*log|V|) である必要があるため、ダイクストラのアルゴリズムを使用する必要があると思います。
このグラフの s から v への最短パスが、指定されたグラフで必要な最短パスと同等になるように、与えられたグラフを非負の重みを持つ新しいグラフに何らかの方法で変換する必要があると推測しています..または多分私は必要ですダイクストラのアルゴリズムをどうにか修正するには??
少し考えてみましたが、今はアイデアがありません... :(