5000个节点中500个节点的两两配对的最短路径问题

最近我在求解这样一个问题:
一个图G有5000个节点，
其中一个子集G2有500个节点，
求G2种所以两点间的最短路径.

首先我用bi-direction bsf求指定两点之间的shortest path
然后发现很慢，因为有些点之间要访问90%以上的节点之后才能确定最短路径，
所以我加上优化，在求解一组的时候，同时发现其他需要求解的组。这样稍微快一点。
但是一开始一个查找（大概5秒不到），可以找到300组结果，但是后来只能找到1组结果，
越来越慢，运行了6个多小时后还是不见结束的意思。
于是我试试看对5000节点使用Floyd-Warshall算法，但是看了要用100小时，虽然是现实的，但是还是很长。

后来我在Bidirectional search的时候加上Depth-limited search，就是深度超过5的时候就放弃，这也是现实的， 这样发现很快了。

但是之后的问题也许还没有彻底解决。