Блог

я пытаюсь найти кратчайший путь от вершины к другой. Чтобы быть более точным, у меня есть ориентированный граф, и, всегда переходя в нем «вперед», я всегда буду в конечном итоге. Что-то вроде структуры нейронной сети. Я решил найти кратчайший путь с помощью рекурсии, которая отлично работала с меньшими числами. Но для больших данных я получаю SIGSEGV. Я почти уверен, что это переполнение стека. У кого-нибудь из вас есть идеи, как я могу переключиться с простого повторения на что-то, что не вызовет проблем?

 int findShortestPath(Vertex * v, int endPointX){
    if(v->isShortestPathSet())
        return v->getShortestPath();
    vector<int> * paths = new vector<int>;
    if(v->getEndPos() == endPointX)
        return 0;
    for(int i = 0; i < v->getOutputEdges().size(); i   ){
        Edge * outputEdge = v->getOutputEdges().at(i);
        paths->push_back(findShortestPath(outputEdge->getOutputVertex(), endPointX)   outputEdge->getValue());
    }
    int minPath = paths->at(0);
    for(int i = 0; i < paths->size(); i   ){
        if(paths->at(i) < minPath)
            minPath = paths->at(i);
    }
    v->setShortestPath(minPath);
    free(paths);
    return minPath;
}
  

это функция, с помощью которой я ищу кратчайший путь. Он определяет кратчайший возможный путь к каждой вершине, поэтому в дальнейших запросах мне не придется повторять эти дорогостоящие вычисления.

Вы можете реализовать алгоритм Дейкстры итеративно. Вот фрагмент кода, который итеративно реализует алгоритм Дейкстры

 #include <queue>
#include <unordered_map>
#include <vector>

using IntPair = std::pair<int,int>;
std::priority_queue<IntPair, std::vector<IntPair>, std::greater<IntPair>> pq;
std::unordered_map<int, std::unordered_map<int, int>> g;
std::vector<int> distance, parent;

void dijkstras(int startVertex) {
    // insert the startVertex into the priority queue(pq)
    pq.push(std::make_pair(0, startVertex));

    while (!pq.empty()) {
        // select the vertex with least distance travelled so far from the pq
        // and then, pop the selected vertex from pq
        auto [dist, src] = pq.top(); pq.pop();
        // iterate on all its neighbours and update distance[] and parent[]
        for (auto [v, weight] : g[src]) {
            if (int newDist = dist   weight; newDist < distance[v]) {
                parent[v] = src;
                distance[v] = newDist;
                pq.push(std::make_pair(newDist, v));
            }
        }
    }
}
  

Здесь,

• pq является приоритетной очередью, в которой хранятся пары (distanceTravelledSoFar, previousNode) . Здесь pq действует как минимальная куча, которая помогает нам оптимально выбрать следующий узел
• g это просто список смежности, который вы используете для хранения графика
• distance является массивом кратчайших расстояний пути к каждой из вершин из startVertex
• parent это массив, в котором хранится предыдущий узел по кратчайшему пути к каждой вершине из startVertex

Вот ссылка на код, который я использовал для решения этого вопроса

Ответ на ваш вопрос предлагается в комментариях (и Херувим дает хороший пример алгоритма Дейкстры.

Я также отвечу, изменив ваш код. Во-первых, я думаю, что геттеры и сеттеры не нужны, и вы должны использовать современный C . Поэтому я изменил ваш код следующим образом:

 #include <vector>
#include <algorithm>
#include <optional>

class Vertex;

struct Edge {
    Vertex* const outputVertex;
    int const value;
};

struct Vertex {
    int const endPoint;
    std::vector<Edge const*> const outputEdges;
    std::optional<int> shortestPath;
};

int findShortestPath(Vertex* const v, int endPoint){
    if(v->endPoint == endPoint) return 0;
    if(v->shortestPath.has_value()) return v->shortestPath.value();
    auto constamp; outputEdges = v->outputEdges; // hopefully prevent one layer of indirection
    std::vector<int> paths; paths.reserve(outputEdges.size());
    std::transform(cbegin(outputEdges), cend(outputEdges), back_inserter(paths),
       [endPoint] (Edge const* const outputEdge) { 
           return findShortestPath(outputEdge->outputVertex, endPoint)   outputEdge->value;
            });
    return v->shortestPath.value() = *std::min_element(cbegin(paths), cend(paths));
}
  

Теперь, чтобы реализовать стек, вам нужно изменить концепцию, которую вы используете: вместо рекурсивного перехода в глубину и возврата расстояния, вы передаете расстояние вперед. Вместе со стеком, предложенным в комментариях, это приведет к следующему коду:

 #include <stack>
#include <utility>
#include <climits>

int findShortestPath(Vertex const* const startVertexPtr, int endPoint) {
    int minDistance = INT_MAX;
    std::stack<std::pair<Vertex const*, int>> s;
    s.push(std::make_pair(startVertexPtr, 0));
    while(!s.empty()) {
        auto [vertexPtr, distance] = s.top(); s.pop(); // structured binding
        if (vertexPtr->endPoint == endPoint) {
            minDistance = std::min(minDistance, distance); // end is found, see if it's path has minimum distance
            continue;
        }
        for(Edge const* const edge : vertexPtr->outputEdges) {
            s.push(std::make_pair(edge->outputVertex, distance   edge->value)); // pass the distance forward
        }
    }
    return minDistance;
}
  

… но вы видите, что я здесь не использую Vertex::shortestPath , что предложило бы оптимизацию. Я не полностью проверил это, но вы, вероятно, можете сделать что-то вроде этого:
Сначала я снова переопределяю Vertex

 struct Vertex {
    int const endPoint;
    std::vector<Edge const*> const outputEdges;
    int shortestPath = INT_MAX;
};
  

И затем:

 int findShortestPath(Vertex const* const startVertexPtr, int endPoint) {
    int minDistance = INT_MAX;
    std::stack<std::pair<Vertex const*, int>> s;
    s.push(std::make_pair(startVertexPtr, 0));
    while(!s.empty()) {
        auto [vertexPtr, distance] = s.top(); s.pop();
        if (vertexPtr->endPoint == endPoint) {
            minDistance = std::min(minDistance, distance);
            continue;
        }
        for(Edge const* const edge : vertexPtr->outputEdges) {
            Vertexamp; vertex = *edge->outputVertex; // hopefully one less level of indirection
            auto newDistance = distance   edge->value;
            if (newDistance < vertex.shortestPath) {
                vertex.shortestPath = newDistance;
                s.push(std::make_pair(amp;vertex, newDistance));
            }
        }
    }
    return minDistance;
}
  

Но, вероятно, возможно больше оптимизаций.