無向加重スパースグラフのすべてのペアの最短パス長を見つけるための最良のアルゴリズムは何ですか? 具体的には、重みはノード間の距離です (したがって、正の値になります)。パスの長さだけが必要であることに注意してください (つまり、パス自体ではありません)。私のグラフはまばらなので、隣接リストとして保存されます。
Dijkstra、Floyd-Warshall、Johnson などを見つけましたが、いずれも私の目的に最適ではないようです。Dijkstra の場合、すべての頂点に対して単一ソース バージョンを実行します。Floyd-Warshall は高密度グラフ用で、Johnson は有向グラフ用です。
特に C++ での実装を探しています。
ジョンソンのアルゴリズムは、まばらなグラフに最も適しているようです (|V| > |E| の場合、FW の O(V^3) とは対照的に、O(V^2logV) になります)。ただし、ジョンソンのアルゴリズムは最初のステップで重みを非負にする (これは必要ありません) ため、正しく指摘したように 2 番目のステップのみを実行できます。これは基本的に各ノードからのダイクストラだけです。ここの最後のスライドで述べたように、それは O(VElogV) だけを取る必要があります。それが最良の解決策であることを証明できるかどうかはわかりませんが、(負でない重みの最短経路を見つけるための) より良い解決策があったとしたら、ジョンソンのアルゴリズムが重みを書き換えた後にそれを使用することを期待しています。
有向グラフで機能するという事実は気にする必要はありません.無向グラフを有向グラフに変換するには、無向グラフを有向グラフに変換するだけで、2 つの有向辺を行ったり来たりします (単純な O(E) 時間で)。つまり、スペースの制約がない限り。