ここで問題があります。あるノードから別のノードへのグラフ内のすべての最短経路を見つけようとしています。すでにダイクストラを実装していますが、それらすべてを見つける方法は本当にわかりません。
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;
}
これは私たちのコードです。変更する必要があると考えていますが、実際にはどこにあるのかわかりません。