導入する代わりに
いわば、古い「メモ」を整理し、これに出くわしました。 まだハブに招待していませんが、私は考えて、公開することにしました。 この記事では、グラフ内の特定の頂点から最短パスを見つけるためのダイクストラのアルゴリズムを理解する方法を説明します。 グラフの幅を横断するアルゴリズムから自然に彼に何が来るのでしょうか。
コメントの中で、彼らは私に、STL C ++のpriority_queueの背後に隠されたデータ構造についてもっと話をするように頼みました。 記事の最後に短いストーリーとその実装があります。
バイパス幅を数える
私が説明したい、そして間違いなく見逃せない最初のアルゴリズムは、widthでグラフをトラバースすることです。 これは何？ グラフの正式な記述から少し離れて、そのような画像を想像してみましょう。 可燃性のものを含浸させた地面のロープの上に、同じ長さのものを敷設して、それらのいずれも交差しないようにしますが、一部は互いに接触します。 次に、いずれかの端に火をつけます。 火はどのように振る舞いますか？ 彼はすべてが点灯するまで、ロープで隣接する交差点に均等にジャンプします。 この図を3次元空間に一般化するのは簡単です。 これはまさに、グラフの幅のトラバースが実際にどのように見えるかです。 次に、より正式に説明します。 ある頂点Vから幅方向に歩き始めたと仮定します。次に、頂点Vの近傍を調べます（Vと共通のエッジを持つ頂点をVの近傍と呼びます）。 グラフ内のすべての頂点が表示されるまで続きます。
幅クロールの実装
幅をトラバースするプロセスで頂点にいる場合、キューを使用して、既に訪れたものを除く頂点のすべての隣接点を追加します。
void bfs(int u) { used[u] = true; queue<int> q; q.push(u); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < (int) g[u].size(); i++) { int v = g[u][i]; if (!used[v]) { used[v] = true; q.push(v); } } } }
この実装では、gは隣接する頂点のリストです。 g [u]には、u（std :: vectorがリストとして使用された）を持つ隣接する頂点のリストが含まれます。使用された配列は、既に訪れた頂点を理解できる配列です。 ここでは、幅優先のウォークは幅ラップそのもの以外は何もしません。 どうしてだろう？ ただし、必要なものを検索するために簡単に変更できます。 たとえば、任意のピークから他のすべてのピークまでの距離とパス。 リブには重量がない、つまり グラフは重み付けされません。 以下は、距離とパスの検索の実装です。
void bfs(int u) { used[u] = true; p[u] = u; dist[u] = 0; queue<int> q; q.push(u); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < (int) g[u].size(); i++) { int v = g[u][i]; if (!used[v]) { used[v] = true; p[v] = u; dist[v] = dist[u] + 1; q.push(v); } } } }
ここで、pは祖先の配列です。 p [v]には頂点vの祖先が含まれ、dist [v]は頂点vまでのウォークを開始した頂点からの距離です。 パスを復元する方法は？ これは、必要なピークの祖先の配列を単純に調べるだけで、非常に簡単です。 たとえば、再帰的に：
void print_way(int u) { if (p[u] != u) { print_way(p[u]); } cout << u << ' '; }
最短経路
エッジの重みが負でない場合にのみ、それ以降のすべての考慮事項が当てはまります。
それでは、重み付きグラフに移りましょう。 グラフのエッジには重みがあります。 たとえば、リブの長さ。 またはそれを通過するための料金。 またはそれを通過するのにかかる時間。 タスクは、ある頂点から別の頂点への最短パスを見つけることです。 この記事では、幅を歩き回ることから始めますが、他の場所でそのようなアプローチを見たことを覚えていません。 たぶん見逃した。 そのため、幅の回避策の実装、具体的にはキューへの追加の条件をもう一度見てみましょう。 幅を歩き回って、まだキューに行っていない頂点のみを追加します。 次に、この条件を変更し、距離を縮めることができる頂点を追加します。 明らかに、距離を縮めることができる頂点が残っていない場合にのみ、キューは空になります。 頂点Vからのパスを減少させるプロセスは、頂点Vの緩和と呼ばれます。
最初は、すべてのピークへのパスが無限大に等しいことに注意してください（無限大の場合、十分に大きな値を取ります。つまり、無限大の値よりも長いパスはありません）。 このアルゴリズムは、幅の広い回避策から直接続きます。グラフの最短経路で人生で最初の問題を解決したのは、彼にとってのことでした。 このメソッドは、アルゴリズムを開始した先頭から他のすべてへの最短パスを検索することに言及する価値があります。 実装を提供します。
const int INF = 1e+9; vector< pair<int, int> > g[LIM]; // g[u] : ( u v, v) void shortcut(int u) { fill(dist, dist + n, INF); dist[u] = 0; p[u] = u; queue<int> q; q.push(u); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < (int) g[u].size(); i++) { int v = g[u][i].second, len = g[u][i].first; if (dist[v] > dist[u] + len) { p[v] = u; dist[v] = dist[u] + len; q.push(v); } } } }
なぜこのようなペアを隣接リストに保持するのですか？ このアルゴリズムを改善すると、少し後に明らかになりますが、率直に言って、 この実装では、ペアを保存でき、その逆も可能です。 キューイングはわずかに改善できます。 これを行うには、bool配列を起動して、リラックスする頂点が現在キューにあるかどうかをマークします。
const int INF = 1e+9; vector< pair<int, int> > g[LIM]; bool inque[LIM]; void shortcut(int u) { fill(dist, dist + n, INF); dist[u] = 0; p[u] = u; queue<int> q; q.push(u); inque[u] = true; while (!q.empty()) { int u = q.front(); q.pop(); inque[u] = false; for (int i = 0; i < (int) g[u].size(); i++) { int v = g[u][i].second, len = g[u][i].first; if (dist[v] > dist[u] + len) { p[v] = u; dist[v] = dist[u] + len; if (!inque[v]) { q.push(v); inque[v] = true; } } } } }
よく見ると、このアルゴリズムはLeviticanアルゴリズムと非常によく似ていますが、それでもそうではありませんが、最悪の場合は同じ漸近性で機能します。 これを大まかに評価しましょう。 最悪の場合、エッジを通過するたびにリラクゼーションを実行する必要があります。 合計O（n * m）。 評価はかなり大雑把ですが、初期段階ではこれで十分です。 また、これはまさに最悪のケースであり、実際には、そのような実装でさえ非常に迅速に機能することに注意する価値があります。 そして今、最も興味深い！...ドラムロール...アルゴリズムをダイクストアルゴリズムにアップグレードしましょう！
ダイクストラのアルゴリズム
頭に浮かぶ最初の最適化。 そして、それらのピークを緩和しましょう、今までの道は最小限です？ 実際、ある日私が思いついたのはこの考えでした。 しかし、結局のところ、このアイデアは私にとって最初のものではありませんでした。 最初に彼女は素晴らしい科学者エドガー・ダイクストラに来ました。 さらに、この方法でリラクゼーションのピークを選択すると、リラクゼーションをn回しか実行しないことを証明したのは彼でした！ 直感的なレベルでは、ピークへのパスが最小になった場合、それをさらに減らすことはできないことは明らかです。 こちらまたはウィキペディアで正式に読むことができます。
最小距離でピークを効果的に検索する方法を理解するために、問題は小さなものに任されています。 これを行うには、優先度キュー（ヒープ、ヒープ）を使用します。 stlには、それを実装するクラスがあり、 priority_queueと呼ばれます 。 実装を示しますが、これも以前のアルゴリズム（この記事で説明）から直接続きます。
void dijkstra(int u) { fill(dist, dist + n, INF); dist[u] = 0; p[u] = u; priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q; q.push(make_pair(0, u)); while (!q.empty()) { pair<int, int> u = q.top(); q.pop(); if (u.first > dist[u.second]) continue; for (int i = 0; i < (int) g[u.second].size(); i++) { int v = g[u.second][i].second, len = g[u.second][i].first; if (dist[v] > dist[u.second] + len) { p[v] = u.second; dist[v] = dist[u.second] + len; q.push(make_pair(dist[v], v)); } } } }
ほとんどの場合、ここで何が起こっているのか完全に明確ではありません。 優先キューを宣言することから始めましょう。 ここで、テンプレートの最初の引数はキューに格納されるデータ、具体的にはフォームのペア（最上部までの距離、頂点番号）、テンプレートの2番目の引数はデータが格納されるコンテナ、3番目の引数、コンパレータ（ヘッダーファイルにあります）機能的）。 他のコンパレータが必要なのはなぜですか？ 標準宣言priority_queue <pair <int、int >>を使用すると、最大距離の頂点のみを取得することができますが、他の方法が必要です。 このような提起された問題の解決策の漸近はO（n * log（n）+ m * log（n））です。
実際、合計でn個の緩和があり、log（n）の最小パス長を持つ頂点を探します（これは優先度stlの標準キューの漸近的な動作です）。 また、キューに同じ頂点を追加したが、パスが異なることが判明する場合があることに注意してください。 たとえば、隣接点に頂点Cがある頂点Aからリラックスし、次に隣接点に頂点Cもある頂点Bからリラックスし、これに関連する問題を回避するために、単純に頂点をスキップしますキューから出たが、関連のないキューからの距離、すなわち 現在の最短よりも多く。 このため、実装には（u.first> dist [u.second]）が続く場合の行が含まれます。 。
結論の代わりに
O（n * log（n）+ m * log（n））に対してダイクストラを書くのは実際には非常に簡単であることがわかりました！
追加
コメントでは、自分の手でpriority_queueを実行する方法を説明するように頼まれました。
次の問題に直面しましょう（ダイクストラのアルゴリズムのように）。
次の要件を満たすデータ構造を維持する必要があります。
1）O（log（n））時間以下を追加します。
2）O（log（n））時間以内に最小要素を削除します。
3）O（1）時間の最小値を検索します。
これらの要件は、ロシア語の文献では通常「ヒープ」と呼ばれる、英語の「ヒープ」または「優先度キュー」のデータ構造によって満たされていることがわかります。
一般的に、ヒープはツリーです。 このツリーのプロパティをさらに詳しく見てみましょう。 すでにヒープが構築されていると仮定し、次のように定義します。ヒープ内の各頂点について、この頂点の要素がその子孫の要素より大きくないことは事実です。 次に、最小要素はツリーのルートにあります。これにより、将来O（1）の最小値を検索できます。
残りのプロパティが満たされるように、ヒープを再定義しましょう。 ツリーの頂点のレベルをルートからルートまでの距離と呼びましょう。 前のレベルが完全にいっぱいになるまで、ヒープに新しいレベルを追加することは禁止されています。 より正式には、現在の最大ツリーの高さをHとし、高さH + 1に頂点を追加することは禁止されていますが、高さHに追加することは可能です。実際、このような条件下では、ヒープの高さは常にO（log（n））以下です。
ヒープ内のアイテムを追加および削除する方法を学習する必要があります。
バイナリツリーにヒープを実装します。このツリーでは、子孫の数が2未満の頂点は1つしかありません。 ツリーを配列に格納し、位置posの頂点の子孫は位置2 * posおよび2 * pos + 1にあり、親はpos / 2にあります。
現在の最大レベルで最初の空いている場所に要素を追加してから、ふるい分けと呼ばれる操作を実行します。 これは、追加された要素の親が要素自体よりも大きい間、追加された要素と親の位置を変更し、ルートまで再帰的に繰り返すことを意味します。 この場合、ヒーププロパティに違反していないことを証明しましょう。 現在の要素は親よりも小さいため、単純であり、親のすべての子孫よりも小さくなっています。
void push(const value_t& value) { data.push_back(value); sift_up(data.size() - 1); } void sift_up(size_t position) { size_t parent_position = position / 2; if (!cmp(data[position], data[parent_position])) { swap(data[position], data[parent_position]); sift_up(parent_position); } }
最小要素を次のように削除します。最初に、ツリーのルートを最大レベルの最後の要素と交換し、次にこの要素があった頂点を削除します（最小値になります）。 その後、ヒープのプロパティに違反するため、それらを復元するには、シフティングダウンと呼ばれる操作を実行する必要があります。 ルートから再帰的に開始します。現在の要素については、子孫から最小値を見つけ、現在の要素を交換し、現在の要素が変更された頂点から再帰的に開始します。 この操作の後、ヒーププロパティが実行されることに注意してください。
void pop() { swap(data[1], data.back()); data.pop_back(); sift_down(1); } void sift_down(size_t position) { size_t cmp_position = position; if (2 * position < data.size() && !cmp(data[2 * position], data[cmp_position])) { cmp_position = 2 * position; } if (2 * position + 1 < data.size() && !cmp(data[2 * position + 1], data[cmp_position])) { cmp_position = 2 * position + 1; } if (cmp_position != position) { swap(data[cmp_position], data[position]); sift_down(cmp_position); } }
ツリーの高さはO（log（n））なので、Oの追加と削除は機能します（log（n））。
全コード
template<typename value_t, typename cmp_t> class heap_t { public: heap_t() : data(1) { } bool empty() const { return data.size() == 1; } const value_t& top() const { return data[1]; } void push(const value_t& value) { data.push_back(value); sift_up(data.size() - 1); } void pop() { swap(data[1], data.back()); data.pop_back(); sift_down(1); } private: void sift_up(size_t position) { size_t parent_position = position / 2; if (!cmp(data[position], data[parent_position])) { swap(data[position], data[parent_position]); sift_up(parent_position); } } void sift_down(size_t position) { size_t cmp_position = position; if (2 * position < data.size() && !cmp(data[2 * position], data[cmp_position])) { cmp_position = 2 * position; } if (2 * position + 1 < data.size() && !cmp(data[2 * position + 1], data[cmp_position])) { cmp_position = 2 * position + 1; } if (cmp_position != position) { swap(data[cmp_position], data[position]); sift_down(cmp_position); } } cmp_t cmp; vector<value_t> data; };