使用线性代数或BFS求图的直径

Question

我收到学校的作业，说我需要在CPP中找到一个图的直径。问题是，我需要为5000个图做这件事，每个图有1000个顶点。为了保存我的图形，我使用了这样的矢量：

std::vector<std::vector<int>> graph

我能够在每个顶点上使用BFS找到图的直径；最长最短"；路径，但它真的很慢，因为非常复杂

所以我在网上读到，我可以使用线性代数来找出直径是多少，但这值得吗？最后计算需要同样的时间吗？

另外，这是否意味着我必须从一个向量中的向量变成这样的矩阵？

bool** graph

感谢您对的帮助

Answer 1

我能想到的最快的算法是众所周知的Floyd-Warshall算法，它的复杂性为O(N^3)(N是顶点数(。它计算所有顶点对之间的最短路径长度。

对于1000个顶点图的情况，时间是相当实惠的——大约10亿步，在现代CPU上，每个图的算法需要几秒钟，我希望你能负担得起这个时间。该算法将使用10亿个非常简单的步骤-3个缓存读取+1个添加+1个比较+1个缓存分配。

接下来的C++代码做整个循环-从字符串流中输入，初始化权重，运行Floyd-Warshall算法计算所有顶点对之间的最短距离，找到最大最短距离并输出结果。

多个图形可以在不同的CPU内核上轻松地同时计算，这将使整个计算速度提高数倍。

我的算法支持边的任何整数权重，甚至是负权重。算法的输入应该具有权重矩阵NxN大小(N是顶点的数量(，零权重表示没有边(即无限距离(。

在线试用！

#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
int main() {
std::string inps = R"(
0 0 2 0
4 0 3 0
0 0 0 2
0 1 0 0
)";
std::stringstream inp;
inp.str(inps);
size_t const inf = size_t(-1) >> 2; // Infinity
std::vector<std::vector<size_t>> d; // Distance matrix
// Input
std::string line;
while (std::getline(inp, line)) {
if (line.find_last_not_of(" rnt") == std::string::npos)
continue;
d.resize(d.size() + 1);
std::stringstream ss;
ss.str(line);
size_t x = 0;
while (ss >> x)
d.back().push_back(x);
}
// Compute shortest distances. Algo https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
for (size_t i = 0; i < d.size(); ++i)
for (size_t j = 0; j < d[i].size(); ++j)
if (d[i][j] == 0 && i != j)
d[i][j] = inf;
for (size_t k = 0; k < d.size(); ++k)
for (size_t i = 0; i < d.size(); ++i)
for (size_t j = 0; j < d.size(); ++j)
d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
// Find longest distance.
size_t maxd = 0, maxi = 0, maxj = 0;
for (size_t i = 0; i < d.size(); ++i)
for (size_t j = 0; j < d.size(); ++j)
if (maxd < d[i][j]) {
maxd = d[i][j];
maxi = i;
maxj = j;
}
// Output
std::cout << "diameter " << maxd << " from vertex " << maxi << " to " << maxj << std::endl;
}

输出：

diameter 7 from vertex 2 to 0

可以看出，它发现从顶点2到顶点0的直径(最长最短路径长度(等于7。