優先度キュー (ヒープ) を使用せずに、循環加重グラフで Djikstra のアルゴリズムを使用しようとしましたが、うまくいきました。
ウィキペディアによると、このアルゴリズムの元の実装は優先キューを使用せず、O(V 2 ) 時間で実行されます。
ここで、プライオリティ キューを削除して通常のキューを使用した場合、実行時間は線形、つまり O(V+E) になります。
プライオリティ キューが必要な理由を誰か説明できますか?
質問する
17794 次
4 に答える
11
私はまったく同じ疑問を抱いており、priority_queue のないアルゴリズムが機能しないというテスト ケースを見つけました。
頂点から頂点に重みでエッジを追加gするメソッドである Graph オブジェクトがあるとします。addEdge(a,b,w)abw
さて、次のグラフを定義しましょう:-
Graph g
g.addEdge(0,1,5) ;
g.addEdge(1,3,1) ;
g.addEdge(0,2,2) ;
g.addEdge(2,1,1) ;
g.addEdge(2,3,7) ;
ここで、キューに次の順序でノードが含まれているとし{0,1,2,3 }
ます。つまり、ノード 0 が最初にアクセスされ、次にノード 1 がアクセスされます。
この時点で、dist b/w 0 と 3 は path を使用して 6 として計算され0->1->3、1 は訪問済みとしてマークされます。
ここで、ノード 2 が訪問され、dist b/w 0 and 1 が path を使用して値 3 に更新されます0->2->1が、ノード 1 が訪問済みとしてマークされているため、距離 b/w 0 および 3 を変更することはできません (最適パスを使用) ( `0->2->1->3) は 4 です。
そのため、priority_queue を使用しないとアルゴリズムが失敗します。
dist b/w 0 と 3 は 6 であると報告されていますが、実際には 4 である必要があります。
さて、これがアルゴリズムの実装に使用したコードです:-
class Graph
{
public:
vector<int> nodes ;
vector<vector<pair<int,int> > > edges ;
void addNode()
{
nodes.push_back(nodes.size()) ;
vector<pair<int,int> > temp ; edges.push_back(temp);
}
void addEdge(int n1, int n2, int w)
{
edges[n1].push_back(make_pair(n2,w)) ;
}
pair<vector<int>, vector<int> > shortest(int source) // shortest path djkitra's
{
vector<int> dist(nodes.size()) ;
fill(dist.begin(), dist.end(), INF) ; dist[source] = 0 ;
vector<int> pred(nodes.size()) ;
fill(pred.begin(), pred.end(), -1) ;
for(int i=0; i<(int)edges[source].size(); i++)
{
dist[edges[source][i].first] = edges[source][i].second ;
pred[edges[source][i].first] = source ;
}
set<pair<int,int> > pq ;
for(int i=0; i<(int)nodes.size(); i++)
pq.insert(make_pair(dist[i],i)) ;
while(!pq.empty())
{
pair<int,int> item = *pq.begin() ;
pq.erase(pq.begin()) ;
int v = item.second ;
for(int i=0; i<(int)edges[v].size(); i++)
{
if(dist[edges[v][i].first] > dist[v] + edges[v][i].second)
{
pq.erase(std::find(pq.begin(), pq.end(),make_pair(dist[edges[v][i].first],edges[v][i].first))) ;
pq.insert(make_pair(dist[v] + edges[v][i].second,edges[v][i].first)) ;
dist[edges[v][i].first] = dist[v] + edges[v][i].second ;
pred[i] = edges[v][i].first ;
}
}
}
return make_pair(dist,pred) ;
}
pair<vector<int>, vector<int> > shortestwpq(int source) // shortest path djkitra's without priority_queue
{
vector<int> dist(nodes.size()) ;
fill(dist.begin(), dist.end(), INF) ; dist[source] = 0 ;
vector<int> pred(nodes.size()) ;
fill(pred.begin(), pred.end(), -1) ;
for(int i=0; i<(int)edges[source].size(); i++)
{
dist[edges[source][i].first] = edges[source][i].second ;
pred[edges[source][i].first] = source ;
}
vector<pair<int,int> > pq ;
for(int i=0; i<(int)nodes.size(); i++)
pq.push_back(make_pair(dist[i],i)) ;
while(!pq.empty())
{
pair<int,int> item = *pq.begin() ;
pq.erase(pq.begin()) ;
int v = item.second ;
for(int i=0; i<(int)edges[v].size(); i++)
{
if(dist[edges[v][i].first] > dist[v] + edges[v][i].second)
{
dist[edges[v][i].first] = dist[v] + edges[v][i].second ;
pred[i] = edges[v][i].first ;
}
}
}
return make_pair(dist,pred) ;
}
予想通り、結果は次のとおりでした:-
priority_queue あり
0
3
2
4
現在優先キューなしで使用中
0
3
2
6
于 2015-01-24T04:17:51.697 に答える
3
Moataz Elmasry が言ったように、期待できる最善の方法は O(|E| + |V|.|logV|) であり、fib キューがあります。少なくとも大きなああの値になると。
その背後にある考え方は、現在作業しているすべての頂点 (ノード) について、最短パスをすでに見つけているということです。頂点が最小 (距離 + エッジの重み) ではない場合、必ずしもそうではありません。これにより、最初の頂点から到達可能なすべての頂点を拡張 (?) するとすぐにアルゴリズムを停止できます。最小の頂点を展開していない場合、最短パスを見つけることが保証されていないため、1 つだけでなく、すべてのパスをテストする必要があります。したがって、1 つのパスだけですべてのエッジを通過する必要はなく、すべてのパスのすべてのエッジを通過します。
O(E + V) の見積もりはおそらく正しいですが、一方、決定したパスとコストは正しくありません。私が間違っていなければ、すべての頂点から移動する最初のエッジがたまたま最小のエッジである場合にのみ、パスは最短になります。
したがって、優先度のあるキューを使用しないダイクストラの最短パス アルゴリズムは、ダイクストラのパス アルゴリズムにすぎません ;)
于 2013-05-16T14:40:49.557 に答える
2
スパースグラフの場合、バイナリ最小ヒープランタイムis（E * logV）で実装すると、フィボナッチヒープで実装すると、ランタイムは（VlogV + E）になります。
于 2012-12-13T01:31:51.837 に答える
0
ヒープは、キューにエッジを追加し、最上位の要素を削除するために O(log(n)) を保証するため、このタスクに最適な選択です。プライオリティ キューの他の実装では、キューに追加するか、キューから削除して、他の場所でパフォーマンスを向上させることを犠牲にします。グラフがどれだけまばらであるかによっては、優先度キューの別の実装を使用してパフォーマンスが向上する場合がありますが、一般的に言えば、最小ヒープが 2 つのバランスを取るため最適です。
最大の情報源ではありませんが: http://en.wikipedia.org/wiki/Heap_(data_structure)
于 2012-11-18T03:05:30.433 に答える