The fastest algorithm that I can come up with is well known Floyd-Warshall algorithm, which has complexity O(N^3) (N is number of vertices). It computes shortest paths lengths between all pairs of vertices.
For the case of your 1000-vertices graphs the time is quite affordable - around 1 billion steps, which will take several seconds for this algorithm per graph on modern CPUs, I hope you can afford this time. This algorithm will use 1 billion of very simple steps - 3 cache-reads + 1 add + 1 compare + 1 cache-assign.
Next C++ code does whole cycle - does input from string-stream, does initialization of weights, runs Floyd-Warshall algorithm to compute shortest distances between all pairs of vertices, finds maximal shortest distance, outputs results.
Multiple graphs can be easily computed simultaneously on different cores of CPU, which will speedup whole computation several times.
My algorithm supports any integer weights of edges, even negative weights. Input to algorithm should have weights matrix NxN size (N is number of vertices), zero weight denotes that there is no edge (i.e. infinite distance).
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;
}
Output:
diameter 7 from vertex 2 to 0
As one can see it found diameter (longest shortest path length) equal to 7 from vertex 2 to vertex 0.
