2

我正在解决一个问题，我需要在给定的有向未加权图中找到两个节点之间的所有最短路径。我已经使用 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
}

我非常感谢您的大力帮助谢谢，安德拉

4

2 回答 2

2

  1. map<int, map<int,graphNode>* > graph声明一个图，graphNode每条边有一个对象。

    graphNode每个节点有一个类型map<int, map<int,graphNode*> >，或者，甚至更好，map<graphNode*, set /* or vector */<graphNode*> >或者可能更好，multimap< graphNode *, graphNode * >。

    graphNodes 需要存储在与您使用的任何内容不同的结构（例如，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当前父级的第一个子级，这样您就知道下一次停止搜索的机会。

于 2010-04-17T23:21:59.523 回答
1

要编写所有最短路径，您必须编写一个类似于 DFS 的递归算法。运行 BFS 以找到到每个节点的最小距离，将其存储，然后从源节点运行 DFS，仅分支到满足最小路径的节点。每当您到达目标节点时，请写下您到达那里的路径（您在递归函数中一直在跟踪）。请注意，您不会在 DFS 中标记节点。

由于该算法需要回溯，因此最好的方法是通过递归 DFS。您可以使用 BFS 编写它，但您必须维护一个堆栈来跟踪您的回溯，这意味着您实际上是在使用手动维护的堆栈编写 DFS，即使用您需要的两倍代码编写完全相同的算法至。

请注意，最短路径的数量并不总是多项式，因此您可能正在编写指数数量的路径。

于 2014-05-22T13:59:55.677 回答