そこで私は、別のアルゴリズムに頼ることなく、グラフにどのような変更を加えて、ダイクストラのアルゴリズムが機能し、最終的に正しい答えを得ることができるかを考えてきました. それがまったく可能であれば？
私は最初、すべての重みに最も負の重みに等しい定数を追加することを考えましたが、それはすべてを台無しにし、元の単一のソース パスを変更することがわかりました。
次に、グラフをたどって、ゼロ未満のすべての重みを配列またはそのようなものに入れてから、-1 を掛けることを考えました。彼は（実行時間の制約を無視して）うまくいくと思いますが、間違った方法を見ているのかもしれません。
編集：別のアイデア。すべての負の重みを永続的に無限に設定するのはどうですか。そのようにしてそれらが無視されるようにしますか？
ですから、これについていくつかの意見を聞きたいだけです。皆さんはどう思いますか？
ジョンソンのアルゴリズムに似たものを探しているようです:
最初に、新しいノード q がグラフに追加され、重みゼロのエッジによって他のノードのそれぞれに接続されます。
次に、ベルマン・フォード アルゴリズムを使用して、新しい頂点 q から開始し、頂点 v ごとに q から v へのパスの最小重み h(v) を見つけます。このステップで負のサイクルが検出された場合、アルゴリズムは終了します。 .
次に、元のグラフのエッジは、Bellman–Ford アルゴリズムによって計算された値を使用して再重み付けされます。長さ w(u,v) を持つ u から v へのエッジには、新しい長さ w(u,v) + h( が与えられます。 u) − h(v)。
最後に、q が削除され、再重み付けされたグラフ内の各ノード s から他のすべての頂点への最短経路を見つけるために、ダイクストラのアルゴリズムが使用されます。
どのアルゴリズムでも、負のサイクルをチェックし、負のサイクルがない場合は最短経路を見つける必要があります。
あなたの場合、ダイクストラのアルゴリズムを一度実行する必要があります。また、Johnson のアルゴリズムでは、新しく追加されたノードに対してのみ Bellman-Ford アルゴリズムが実行されることに注意してください。(すべての頂点ではありません)。