Нахождение всех кратчайших путей между двумя узлами в невзвешенных ориентированных графах с использованием алгоритма BFS

Question

Я работаю над проблемой, в которой мне нужно найти весь кратчайший путь между двумя узлами в данном ориентированном невзвешенном графе. Я использовал алгоритм BFS для выполнения этой работы, но, к сожалению, я могу напечатать только один кратчайший путь, но не все, например, если это 4 пути с длиной 3, мой алгоритм печатает только первый, но я бы хотел, чтобы он напечатал все четыре кратчайших пути. Мне было интересно в следующем коде, как мне изменить его так, чтобы можно было распечатать все кратчайшие пути между двумя узлами?

class graphNode{
    public:
        int id;
        string name;
        bool status;
        double weight;
};


map<int, map<int,graphNode>* > graph; 


int Graph::BFS(graphNode &v, graphNode &w){

    queue <int> q;
    map <int, int> map1;  // this is to check if the node has been visited or not.
    std::string str= "";
    map<int,int> inQ;  // just to check that we do not insert the same iterm twice in the queue


    map <int, map<int, graphNode>* >::iterator pos;
    pos = graph.find(v.id);
    if(pos == graph.end()) {
        cout << v.id << " does not exists in the graph " <<endl;
        return 1;

    }

    int parents[graph.size()+1];   // this vector keeps track of the parents for the node
    parents[v.id] = -1;


    if (findDirectEdge(v.id,w.id) == 1 ){
        cout << " Shortest Path: " << v.id << " -> " << w.id << endl;
        return 1;
    } //if
    else{
        int gn;
        map <int, map<int, graphNode>* >::iterator pos;

        q.push(v.id);
        inQ.insert(make_pair(v.id, v.id));

        while (!q.empty()){
        gn = q.front();
        q.pop();
        map<int, int>::iterator it;
        cout << " Popping: " << gn <<endl;
        map1.insert(make_pair(gn,gn));


        if (gn == w.id){//backtracing to  print all the nodes if gn is the same as our target node such as w.id
            int current = w.id;
            cout << current << " - > ";
            while (current!=v.id){
                current = parents[current];
                cout << current << " -> ";
            }
        cout <<endl;
        }
                          if ((pos = graph.find(gn)) == graph.end()) {
            cout << " pos is empty " <<endl;
            continue;
        }
        map<int, graphNode>* pn = pos->second;

                          map<int, graphNode>::iterator p = pn->begin();
        while(p != pn->end()) {
            map<int, int>::iterator it;

            it = map1.find(p->first);//map1 keeps track of the visited nodes
            graphNode gn1= p->second;
            if (it== map1.end())    {
                map<int, int>::iterator it1;
                it1 = inQ.find(p->first);  //if the node already exits in the inQ, we do not insert it twice

                if (it1== inQ.end()){
                    parents[p->first] = gn;
                    cout << " inserting " << p->first << " into the queue " <<endl;
                    q.push(p->first);  // add it to the queue
                } //if
            }  //if
            p++;
          } //while

    } //while
}

Я ценю всю вашу большую помощь Спасибо, Andra

Answer 1

1. map<int, map<int,graphNode>* > graph объявляет график с одним graphNode объектом на ребро.

   Один graphNode на узел будет иметь тип map<int, map<int,graphNode*> > или, что еще лучше, map<graphNode*, set /* or vector */<graphNode*> > или, что еще лучше, multimap< graphNode *, graphNode * >.

   graphNode необходимо хранить в отдельной структуре (скажем, vector или deque) от того, что map вы используете.

2. int parents[graph.size()+1]; нестандартно. Вместо этого используйте vector<int> parents( graph.size()+1 );.

3. Чтобы ответить на ваш вопрос, вы хотите продолжить BFS, пока не достигнете первого узла топологического порядка больше первого результата. Введите переменную int first_id_of_next_level = v.id;. (Или лучше используйте указатель.) Когда вы найдете совпадение, добавьте его путь к списку путей. Когда gn == first_id_of_next_level, либо return список, если он не empty, либо установлен first_id_of_next_level = p->first, первый дочерний элемент текущего родителя, так что вы знаете следующую возможность остановить поиск.

Answer 2

Чтобы написать все кратчайшие пути, вы должны написать рекурсивный DFS-подобный алгоритм. Запустите BFS, чтобы найти минимальное расстояние до каждого узла, сохраните его, а затем запустите DFS от исходного узла, разветвляясь только на узлы, которые удовлетворяют минимальному пути. Всякий раз, когда вы достигнете целевого узла, напишите путь, по которому вы его достигли (который вы отслеживали в своей рекурсивной функции). Обратите внимание, что вы не будете отмечать узлы в вашей DFS.

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

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