I am evaluating scalability on various graph algorithms and found that base parallel SSSP algorithms in PBGL does not scale well in my cases. The plots for rmat (scale=20 and 22) are attached. The source code for the benchmark are attached as well.

The main issue that makes me think that I'm doing smth wrong is that execution time of delta stepping algorithm is _increasing_ with node number.  I tried to check the code but has not found anything suspicious.

Can anybody help me with this issue?

Best,

   Alexander