Condition: initial (A) and final (B) vertices, number of vertices (N), edges (M) and graph description are given. It is necessary to find the number of shortest paths from A to B. The graph is not oriented, not weighted (by the long path is meant the number of edges in the path). Restrictions on the input parameters: 1 <= N <10 ^ 5, 0 <= M min (10 ^ 5, N (N-1) / 2). Time limit 1 sec.

The solution is simple: BFS will find the shortest distance and raise the adjacency matrix of this graph to the power of this distance. In the cell [A-1] [B-1] and will be the answer.

But the problem is in speed ... To speed up the exponentiation, I wrote the Strassen algorithm, but it did not help either (unless, of course, I wrote correctly)

Attaching the code and waiting for tips on speeding up (substantial)

#include <iostream> #include <vector> using Graph = std::vector<std::vector<int>>; std::ostream& operator <<(std::ostream &os, const std::vector<std::vector<int>> &other) { for (auto line : other) { for (auto elem : line) { os << elem << " "; } os << std::endl; } return os; } Graph readGraph(int vertex, int edge) { Graph g(vertex); for (int i = 0; i != edge; ++i) { int from, to; std::cin >> from >> to; g[from - 1].push_back(to - 1); g[to - 1].push_back(from - 1); } return g; } std::vector<int> BFS(const Graph &g, int start) { std::vector<int> path(g.size(), -1); path[start] = 0; std::queue<int> q; q.push(start); while (!q.empty()) { auto current = q.front(); q.pop(); for (auto c : g[current]) { if (path[c] == -1) { path[c] = path[current] + 1; q.push(c); } } } return path; } Graph matrixAdj(const Graph &g) { Graph _g(g.size(), std::vector<int>(g.size())); for (int i = 0; i != g.size(); ++i) { for (int j = 0; j != g[i].size(); ++j) { _g[i][g[i][j]] = 1; } } return _g; } Graph matrixMultiply(const Graph &a, const Graph &b) { int size = a.size(); Graph c(size, std::vector<int>(size)); for (size_t i = 0; i != size; ++i) { for (size_t j = 0; j != size; ++j) { c[i][j] = 0; for (size_t k = 0; k != size; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } return c; } Graph operator + (const Graph &a, const Graph &b) { size_t size = a.size(); Graph c(size, std::vector<int>(size)); for (size_t i = 0; i != size; ++i) { for (size_t j = 0; j != size; ++j) { c[i][j] = a[i][j] + b[i][j]; } } return c; } Graph operator - (const Graph &a, const Graph &b) { size_t size = a.size(); Graph c(size, std::vector<int>(size)); for (size_t i = 0; i != size; ++i) { for (size_t j = 0; j != size; ++j) { c[i][j] = a[i][j] - b[i][j]; } } return c; } Graph fastMult(const Graph &a, const Graph &b) { int size = a.size(); Graph c(size, std::vector<int>(size)); if (size == 1) { c[0][0] = a[0][0] * b[0][0]; } else if (size > 64) { size /= 2; Graph a_1(size, std::vector<int>(size)), a_2(size, std::vector<int>(size)), a_3(size, std::vector<int>(size)), a_4(size, std::vector<int>(size)), b_1(size, std::vector<int>(size)), b_2(size, std::vector<int>(size)), b_3(size, std::vector<int>(size)), b_4(size, std::vector<int>(size)), c_1(size, std::vector<int>(size)), c_2(size, std::vector<int>(size)), c_3(size, std::vector<int>(size)), c_4(size, std::vector<int>(size)); for (size_t i = 0; i != size; ++i) { for (size_t j = 0; j != size; ++j) { a_1[i][j] = a[i][j]; a_2[i][j] = a[i][j + size]; a_3[i][j] = a[i + size][j]; a_4[i][j] = a[i + size][j + size]; b_1[i][j] = b[i][j]; b_2[i][j] = b[i][j + size]; b_3[i][j] = b[i + size][j]; b_4[i][j] = b[i + size][j + size]; } } Graph p_1 = fastMult(a_1 + a_4, b_1 + b_4), p_2 = fastMult(a_3 + a_4, b_1), p_3 = fastMult(a_1, b_2 - b_4), p_4 = fastMult(a_4, b_3 - b_1), p_5 = fastMult(a_1 + a_2, b_4), p_6 = fastMult(a_3 - a_1, b_1 + b_2), p_7 = fastMult(a_2 - a_4, b_3 + b_4); c_1 = p_1 + p_4 - p_5 + p_7; c_2 = p_3 + p_5; c_3 = p_2 + p_4; c_4 = p_1 - p_2 + p_3 + p_6; for (size_t i = 0; i != size; ++i) { for (size_t j = 0; j != size; ++j) { c[i][j] = c_1[i][j]; c[i][j + size] = c_2[i][j]; c[i + size][j] = c_3[i][j]; c[i + size][j + size] = c_4[i][j]; } } } else { c = matrixMultiply(a, b); } return c; } int isPow2(int a) { return !(a&(a-1)); } Graph powMatrix(const Graph &a, int power) { int size = a.size(); Graph c = a; for (size_t i = 0; i != power - 1; ++i) { c = fastMult(c, a); } return c; } int main() { int vertex, edge, start, finish; std::cin >> start >> finish >> vertex >> edge; Graph g = readGraph(vertex, edge); auto matrix = matrixAdj(g); if (!(isPow2(vertex))) { while (!(isPow2(vertex))) { ++vertex; } matrix.resize(vertex); for (size_t i = 0; i != vertex; ++i) { if (matrix[i].empty()) { matrix[i] = std::vector<int>(vertex); } else { matrix[i].resize(vertex); } } } auto pathLen = BFS(g, start - 1); int power = pathLen[finish - 1]; matrix = powMatrix(matrix, power); std::cout << matrix[start - 1][finish - 1] << std::endl; return 0; }
  • one
    And which part of the algorithm is slower? Measure. - VladD
  • one
    Strassen will give nothing due to complexity. It is faster asymptotically, but not for real programs, generally speaking. Further, exponentiation can be accelerated to log N - through squaring. But this is all a palliative. We need a fundamentally different algorithm - with such parameters - up to 100,000 - such small movements will not give anything. - Harry
  • Why not modify Dijkstra and keep a list of optimal paths to it at each vertex? - VladD
  • @VladD, and how to choose a priority vertex, if there are no weights? - marka_17
  • @ marka_17: All paths of the same length => all weights are equal to 1. - VladD

2 answers 2

You have an ideological mistake, you have found the shortest path, but to raise the matrix to this power is about n ^ 3 log m operations, the estimate is rough, but if n is about 10'000, it shows that everything is bad.

The idea is this, you let the full BFS. Further dynamics in the graph. For each vertex (in the order of visiting the queue), we count the number of ways to get there. More: when checking that this vertex is not in the queue, we must write the value from the current vertex to this vertex. If it has already been added, add the value of this vertex. Base starting point value is 1.

If you can not realize write questions, I will. I do not post the code yet, so that there would be an opportunity to think.

    I understand in a large number of code, operations on vectors are used, such as adding all the elements of the first and second vectors, and putting all this into the third vector. Std :: valarray is optimized for such operations. In addition, for this class, the operators +, -, etc. have already been defined.

     #include <iostream> #include <valarray> int main (){ std::valarray<int> first = {1, 2, 3, 4, 5, 6}; std::valarray<int> second = {6, 5, 4, 3, 2, 1}; std::valarray<int> third = first + second; for(int i = 0; i < third.size(); ++i){ //7,7,7,7,7,7, std::cout << third[i] << ','; } return 0; }

    Try replacing vector with valarray .