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

Question

我的学校作业说我需要在 CPP 中求出图形的直径。问题是我需要对 5000 个图进行处理，每个图有 1000 个顶点。为了保存我的图表，我使用了这样的 vector vector :

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

我能够在每个顶点上使用 BFS 找到图形的直径并返回“最长最短”路径，但由于非常复杂，它真的很慢

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

另外，这是否意味着我必须从 vector 的 vector 更改为这样的矩阵？

bool** graph

谢谢你的帮助

Answer 1

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

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

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

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

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

Try it online!

#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(" \r\n\t") == 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。