2

与えられた有向非重み付けグラフで2つのノード間のすべての最短経路を見つける必要があるという問題に取り組んでいます。私はBFSアルゴリズムを使用して作業を行いましたが、残念ながら、すべてではなく1つの最短パスしか印刷できません。たとえば、長さが3の4つのパスの場合、アルゴリズムは最初のパスのみを印刷しますが、すべてを印刷したいと思います。 4つの最短経路。次のコードで疑問に思っていたのですが、2つのノード間の最短パスをすべて出力できるように変更するにはどうすればよいですか？

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>* > graphgraphNodeエッジごとに 1 つのオブジェクトを持つグラフを宣言します。

    graphNodeノードごとに 1つのタイプmap<int, map<int,graphNode*> >、またはさらに良いのはmap<graphNode*, set /* or vector */<graphNode*> >、またはさらに良いのはmultimap< graphNode *, graphNode * >です。

    s は、使用するものとは別の構造 (または など)graphNodeに格納する必要があります。vectordequemap

  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か、リストが設定されているため、検索を停止する次の機会がわかります。returnemptyfirst_id_of_next_level = p->first

于 2010-04-17T23:21:59.523 に答える