Since you're doing Monte Carlo anyway, I assume that it would be acceptable to approximate the average shortest-path length. At each step, you could sample a handful of nodes and report the average shortest-path length for paths starting at one of those nodes, which has the same expectation and hopefully reasonable variance.
Alternatively, reference [3] of the JACM paper you mentioned on dynamic shortest-paths is an experimental study from 2004; perhaps the authors would let you use their code.
发布评论
评论（3）
由于无论如何你都在做蒙特卡罗，我认为近似平均最短路径长度是可以接受的。在每一步中，您可以对少数节点进行采样，并报告从这些节点之一开始的路径的平均最短路径长度，该长度具有相同的期望并希望具有合理的方差。
或者，您提到的关于动态最短路径的 JACM 论文的参考文献 [3] 是 2004 年的一项实验研究；也许作者会让你使用他们的代码。
Since you're doing Monte Carlo anyway, I assume that it would be acceptable to approximate the average shortest-path length. At each step, you could sample a handful of nodes and report the average shortest-path length for paths starting at one of those nodes, which has the same expectation and hopefully reasonable variance.
Alternatively, reference [3] of the JACM paper you mentioned on dynamic shortest-paths is an experimental study from 2004; perhaps the authors would let you use their code.
我知道这么晚了，但是你看过LEMON吗？
I know this late, but have you looked at LEMON?
你看过 Boost Graph Library
我没有我自己没有使用过它，但作为 Boost 的一部分，您可以期望它具有非常高的质量，但它需要一定程度的 C++ 专业知识。
Have you looked at Boost Graph Library
I haven't used it myself, but as part of Boost you can expect it to be very high quality, but it will demand a measure of C++ expertise.