以下を格納する必要があるグラフ (隣接リストの実装として格納) アルゴリズムの実装に取り組んでいます。
- 距離の 2 次元 n 対 n 行列 (float の配列として格納)
- 頂点の各ペア間の最短パスの数 (整数の配列として格納)。
- ソースのすべての可能な選択について、ソース頂点として特定の頂点を取るすべての頂点の先行。これは O(n*n*k) です。ここで、k はソース頂点のすべての可能な選択に対するすべての頂点の先行オブジェクトの平均数です。最悪の場合、これは最大 O(n^3) スペースになる可能性があります。ただし、先行者の平均数は少ない可能性があります (k は定数です)。先行は、2 レベルのマップとして格納され、先行のリストは STL ベクトルとして格納されます。
大きなグラフ (>2^12 頂点) でテストを試みましたが、しばらく実行すると std::bad_alloc がスローされます。これは、3GB のメモリのみを使用して 8GB (Ubuntu 12.04) または 16GB で実行した場合でも当てはまります。大規模なテスト ケースを機能させる方法を教えてください。