問題タブ [longest-path]

タイトルが示すように、各ノードが最大で 2 つの入力エッジと 2 つの出力エッジを持つ有向グラフで最長パスを見つける必要があります。その事実が何かに役立つかどうかはわかりません。グラフには最大で 10000 個のノードがあります。そして、ノード 0 からノード 'Exit' までの最長パス (10001) を見つける必要があります。

ダイクストラをコーディングしようとしましたが、うまくいきませんでした。

前もって感謝します。

Floyd-warshall アルゴリズムを使用して、重み付き無向グラフの任意の 2 つの頂点間の最大距離を見つけたいと考えています。このために、私はいくつかの変更を加えました：

1. 正の代わりに負の重みを追加します。

2. 次に、最短経路を見つけます。

しかし、正しい出力が得られません。誰かが私が犯している間違いを指摘できますか.

同じ入力は次のとおりです:-

1[テストケース数]

5 4 [ノード数、エッジ数]

1 2 4 [最初のノード、2 番目のノード、重み]

3 2 3 [最初のノード、2 番目のノード、重み]

2 5 2 [最初のノード、2 番目のノード、重み]

4 1 1 [最初のノード、2 番目のノード、重み]

2 つのノード間の最長パスを取得したい。

ID のステーションがあります ステーションは別のステーションに接続されています。関係は「タクシー」「バス」「ボート」です。

では、全体の最長パスを取得するにはどうすればよいでしょうか? (または最長最短パス) 特定のノードの最長パスは必要ありません。

複数のクエリを試しましたが、多くの場合、「Internal Error...」しか表示されません。

これは私のグラフからの抜粋です (ここでは最短経路): 私の頭の中では、すべてのノードのすべての最短経路を見つけてから、最長最短経路を返す必要があると思います。しかし、私はクエリでそれを取得しません

私は独自の調査を行いましたが、私の要求に対する適切な解決策を見つけることができませんでした.

問題は、私はその負荷を費やす必要があるトラックを持っていることです（ゴミとしましょう）。正のエッジまたは負のエッジになることができる都市（ノード）とエッジ（ウェイ）があります。トラックは道を進んでいますが、選択した道 (エッジ) によっては、緩んだり、より多くの (無駄) を取得する必要がある場合があります。正のエッジを選択した場合は、選択したウェイ値とまったく同じ量の無駄を失います。およびその逆。

したがって、トラックの運転手は一定量のステップを踏む必要があり（エッジの値に関係なく、すべてのステップに一定の時間がかかります）、ドライバーは自宅（起点ノード）に戻る時間が限られています（時間は指定されたパラメーターになります）

したがって、このグラフにはノードがあり、一方向のエッジがあり、このエッジは負または正の値を持つことができ、グラフにはドライバーが使用できるループと使用できないループがあります。また、ノードは異なるエッジでお互いを指すことができます。(A から B へのエッジの値は 5 です) (B から A へのエッジの値は -3 などです..)

そのため、可能な限り最短の時間で最大負荷を使用するための最良の方法をドライバーに提供したいと考えています。

では、問題はこれです。

私が欲しいのは、実際のコードに注意してください。

指定できる問題の名前がわかっている場合は、どういたしまして。独自のアルゴリズムを疑似コードまたは単なる言葉で共有したい場合。こちらもどうぞ。同様の問題が尋ねられると思われるリンクを共有したい場合。こちらもどうぞ。

そして、それが解決できないと思うなら。あなたの考えやそれを証明するリンクを共有してください。

前もって感謝します。