1

Условие: даны начальная(А) и конечная(B) вершины, количество вершин(N), ребер(M) и описание графа. Необходимо найти количество кратчайших путей из А в Б.

Граф не ориентированный, не взвешенный (под длиной пути подразумевается количество ребер в пути).

Ограничения на входные параметры : 1 <= N < 10^5, 0 <= M min(10^5, N(N-1)/2).

Ограничение по времени 1 сек.

Решение по идее простое: BFSом найти кратчайшее расстояние и возвести матрицу смежности данного графа в степень этого расстояния. В ячейке [A-1][B-1] и будет ответ.

Но проблема в скорости... Для ускорения возведения в степень я написал алгоритм Штрассена, но и он не помог(если я, конечно, правильно написал)

Прикрепляю код и жду советов по ускорению (существенному)

#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;
}
7
  • 1
    А какая часть алгоритма медленнее? Измерьте.
    – VladD
    30 июл 2016 в 18:24
  • 1
    Штрассен ничего не даст в силу сложности. Он быстрее асимптотически, но никак не для реальных программ, вообще говоря. Далее, возведение в степень можно ускорить до log N - через возведения в квадрат. Но это все паллиатив. Нужен принципиально иной алгоритм - с такими параметрами - до 100000 - такие мелкие телодвижения ничего не дадут.
    – Harry
    30 июл 2016 в 20:47
  • А почему бы не модифицировать Дейкстру и хранить в каждой вершине список оптимальных путей до неё?
    – VladD
    31 июл 2016 в 3:11
  • @VladD, и каким образом выбирать приоритетную вершину, если весов нет?
    – marka_17
    31 июл 2016 в 12:25
  • @marka_17: Все пути одинаковой длины => все веса равны 1.
    – VladD
    31 июл 2016 в 12:33

2 ответа 2

2

У вас идейная ошибка, вы нашли кратчайший путь, но возводить матрицу в эту степень это порядка n^3 log m операций, оценка грубовата но при n порядка 10'000 показывает что все плохо.

Идея такая, вы пустили полный BFS. Дальше динамика по графу. Для каждой вершины (в порядке посещения очереди) мы считаем число способов туда попасть. Подробнее: при проверке что этой вершины нет в очереди, мы должны записать в эту вершину значение из текущей вершины. Если она уже добавлена, до приплюсовать значение данной вершины. База стартовая точка значение 1.

Если не сможете реализовать пишите вопросы, подскажу. Код пока не выкладываю, что бы была возможность подумать.

1

Я так понимаю в коде в большом количестве используются операции над векторами, типа сложить все элементы первого и второго вектора, и поместить все это в третий вектор. Под такие операции оптимизирован std::valarray. К тому же для этого класса уже определены операторы +, - и т.д.

#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;
}

Попробуйте заменить vector на valarray.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.