3

ここで問題があります。あるノードから別のノードへのグラフ内のすべての最短経路を見つけようとしています。すでにダイクストラを実装していますが、それらすべてを見つける方法は本当にわかりません。

BFS を使用する必要がありますか?

#include <vector>
#include <iostream>
#include <queue>
using namespace std;

typedef pair <int, int> dist_node;
typedef pair <int, int> edge;
const int MAXN = 10000;
const int INF = 1 << 30;
vector <edge> g[MAXN];
int d[MAXN];
int p[MAXN];

int dijkstra(int s, int n,int t){
    for (int i = 0; i <= n; ++i){
        d[i] = INF;  p[i] = -1;
    }
    priority_queue < dist_node, vector <dist_node>,greater<dist_node> > q;
    d[s] = 0;
    q.push(dist_node(0, s));
    while (!q.empty()){
        int dist = q.top().first;
        int cur = q.top().second;
        q.pop();
        if (dist > d[cur]) continue;
        for (int i = 0; i < g[cur].size(); ++i){
            int next = g[cur][i].first;
            int w_extra = g[cur][i].second;
            if (d[cur] + w_extra < d[next]){
                d[next] = d[cur] + w_extra;
                p[next] = cur;
                q.push(dist_node(d[next], next));
            }
        }
    }
    return d[t];
}

vector <int> findpath (int t){
    vector <int> path;
    int cur=t;
    while(cur != -1){
        path.push_back(cur);
        cur = p[cur];
    }
    reverse(path.begin(), path.end());
    return path;
}

これは私たちのコードです。変更する必要があると考えていますが、実際にはどこにあるのかわかりません。

4

1 に答える 1

1

現在、たまたま見つけた最短経路の 1 つだけを保存/取得しています。次の例を検討してください。

4 nodes
0 -> 1
0 -> 2
1 -> 3
2 -> 3

実際、4 番目のノード ( ) には 2 つの以前の有効なノードがp[]あるため、各位置に単一の値を持つことはできないことが明らかになります:と.312

したがって、これを a に置き換えて、vector<int> p[MAXN];次のように機能させることができます。

if (d[cur] + w_extra < d[next]){
    d[next] = d[cur] + w_extra;
    p[next].clear();
    p[next].push_back(cur);
    q.push(dist_node(d[next], next));
}
else if(d[cur] + w_extra == d[next]){
    p[next].push_back(cur); // a new shortest way of hitting this same node
}

また、「分岐」を処理する必要があるため、関数を更新する必要がありますfindpath()。その結果、いくつかの複数のパスが発生し、グラフによっては指数関数的に膨大な量のパスになる可能性があります。パスを印刷する必要があるだけの場合は、次のようにすることができます。

int answer[MAXN];

void findpath (int t, int depth){
    if(t == -1){ // we reached the initial node of one shortest path
        for(int i = depth-1; i >= 0; --i){
            printf("%d ", answer[i]);
        }
        printf("%d\n", last_node); // the target end node of the search
        return;
    }
    for(int i = p[t].size()-1; i >= 0; --i){
        answer[depth] = p[t][i];
        findpath(p[t][i], depth+1);
    }
}

p[s].push_back(-1)ケース間でこのベクトル配列をクリアする以外に、ダイクストラの最初に行う必要があることに注意してください。

于 2013-05-17T18:37:22.397 に答える