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

Question

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

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

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

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

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

bool** graph

感谢您的帮助

Answer 1

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

对于 1000 个顶点的图，时间是相当实惠的 - 大约 10 亿步，对于现代 CPUs 上的每个图，此算法将花费几秒钟，我希望你能负担得起时间。该算法将使用 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。

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

Finding diameter of a graph using linear algebra or BFS

c++

algorithm

breadth-first-search

linear-algebra