すべての最短経路を列挙してください

Question

私は数を見つけて、ソースノードから宛先ノードまでのすべての最短経路を列挙する必要があります。エッジには負の重みが含まれている可能性があります。私はこれを行うためのアルゴリズムを考え出すことができません。

誰かがこれについてどうやって進むかを理解する手助けができますか？

Answer 1

最短経路を見つけるアルゴリズムはよく知られています。最も顕著なのはDijkstra's algorithmです。ダイクストラのアルゴリズムだけが負のエッジ（実際には負のサイクル）を好まない。しかし、Bellman-Fordはそれらを気にせず、実装するのがかなり簡単です。