重み付きグラフの場合、多くのアルゴリズムが提案されています。 たとえば、ある頂点から別の頂点への最短パスを見つけるための一般的なダイクストラアルゴリズム。 これらのアルゴリズムはすべて、共通の基本的な（数学用）機能を備えています-それらは普遍的です。 任意のデザインのグラフに正常に適用できます。 特に、各アルゴリズムの複雑さはわかっています。これは、グラフの頂点の数に応じてアルゴリズムの実行時間が長くなることにほぼ対応しています。 これはすべて、たとえばウィキペディアで詳細に読むことができます。
実用的なタスクに戻りましょう。 道路は重み付きグラフで表されますが、道路はグラフではありません。 つまり、グラフから道路網を構築することはできません。 数学的な抽象化としての仮想グラフとは異なり、道路は実際の素材の人々によって構築され、かなりの費用がかかります。 したがって、それらは可能な限り恐ろしいものではなく、特定の経済的および実用的なルールに従って配置されます。
これらのルールはわかりませんが、道路ネットワークを扱う場合、道路グラフに効果的なアルゴリズムを使用することはかなり可能ですが、普遍的または数学的意味でのグラフには適していません。 ここで、このような2つのアルゴリズムを考えてみましょう。
いくつかの重要な概念と規則
1.エッジの重みが負でない重み付き無向グラフを使用します。 特に、地域（国）内の道路はまさにそのようなグラフです。
2.最短距離行列（MKR）-その小さくて単純な例は、多くの道路地図にあります。 このラベルは通常、「最も重要な都市間の距離」などと呼ばれます。 これは、主対角線の下または上（左上から右下隅）のマトリックスの一部のように見えます。これは、主対角線の反対側にまったく同じ数、つまり、要素M（i、j）= M（j、i）があるためです。 これは、数学者が言うように、グラフが指向性がないために起こります。 行と列は都市（グラフの頂点）に対応しています。 実際には、都市を除くすべての村と交差点がグラフの上部に入るため、このようなテーブルははるかに大きくなりますが、アトラスにそのような大きなテーブルを印刷することは当然不可能です。
まず、テーブルを（精神的に）上部に続け、メインの対角線に対して対称なMKRを取得します。以降、このようなテーブルに留意します。 この場合、特定の番号の列は同じ番号の行と等しくなり、どの概念を使用するかは関係ありません。 両方を使用してそれらを横断します。
MKRは次のいずれかになります。a）MKRを検索する方法の1つで計算したため、事前に知られています。 b）MKPを知らないかもしれませんが、必要に応じて行ごとに決定します。 行ごと-これは、必要な行について、たとえばダイクストラ法によって、それに対応する頂点から残りの頂点までの距離のみが計算されることを意味します。
3.さらにいくつかの概念。 特定の頂点の離心率は、この頂点から最も遠い頂点までの距離です。 グラフの半径は、すべての頂点の最小の離心率です。 グラフの中心は、離心率が半径に等しい頂点です。
実際にどのように見えるか。 道路ネットワークの中心は、ネットワーク内の他のすべてのポイントから最も遠い都市または交差点です。 半径は、この中央ノードから最も遠いノードまでの最大距離です。
4.頂点の度合い-頂点にアタッチされているエッジの数。
道路網のグラフ、すべてのピークの平均次数は2から4の領域にあります。それは非常に自然です-多数の隣接する道路との交差点を構築することは難しく、費用がかかります。 ピークの平均度が低いグラフはスパースと呼ばれます。これは、道路ネットワークのグラフがまさにそのようなものであることがわかります。
タスク1.最短距離のマトリックスでグラフの半径と中心を検索します
グラフには複数の中心がある場合がありますが、それらのいずれかを見つけたいことに注意してください。
一般的な場合、問題はどのように解決されますか？ FIBCの全景。 行の最大要素（各頂点の離心率）が検索され、これらの最大要素から最小値が検出されます。
これは最速の方法からはほど遠いです。 グラフの半径と中心が一度見つかると思われる場合、より高速に何が必要ですか？ たとえば、それらにはタスクとアルゴリズムがあり、列挙中に頂点が絶えずグループに「再結合」され、各グループの基準はその半径です。 この場合、半径は何度も再カウントされ、検索の速度が重要なパラメーターになります。 半径をより速く見つける方法は？
秘密は、道路網のグラフでは、すべての要素を表示する必要がないことです。 実際には、すべての行のごく一部を見てください。
それがどうなるか見てみましょう。 FIBCマトリックスの1つの行の値を検討します。つまり、1つの頂点から他のすべての頂点までの距離を検討します。 グラフの半径がこの行の最大値より大きくてはならず、この行の最小値より小さくてはならないことを証明するのは簡単です。 数学的に言えば、数値の上限と下限を見つけ、それらが一致する場合、数を見つけます。
2つの行AとBのみで値を見つけたとします。さらに、行Aの最大値は行Bの最小値に等しくなります（この値は列Aと行Bの交点にあります）。 Aがグラフの中心であり、見つかった値がその半径であることを証明するのは簡単です。 問題は解決しました。
それは素晴らしいことですが、道路網のグラフ上のそのような状況はありそうになく、この方法で問題を解決することはうまくいきません。 トリッキーになります。
数行のB1とB2を使用します。 それらから、この方法でベクトルMを形成します：M（i）= max [B1（i）、B2（i）]。 すべての行iの値min（M（i））が列Aの最大値に等しい場合、Aが中心であり、見つかったmin（M（i））が半径であることを証明するのは簡単です。
線のペアが十分でない場合、複数の線、たとえば3つを取ることができます：B1、B2、B3、M（i）= max [B1（i）、B2（i）、B3（i）]。 道路網のグラフの特徴は、多くの線が必要ないことです（1ダース以内に収めることが可能です）。 これは、既存のネットワークグラフを実験し、インターネットからダウンロードすることで簡単に確認できます： リンク 。
一般的な場合、そして数学の観点から、これはもちろんそうではありません。 多くの行B（Aを除くほとんどすべて）を使用する必要がある理論的なグラフを作成することはかなり可能です。 この種の実際の道路網を構築することは不可能であるというだけです-十分なお金がありません。
最後のタスクは残ります。 これらの成功した行B1、B2などをすばやく見つける方法 実際の道路網のグラフの場合、これは非常に簡単で迅速です。 これらは、互いに最も遠い頂点になりますが、必ずしも最も遠い頂点ではありません（数学的に言えば、グラフの直径を見つける必要はありません）。 任意の頂点を取得し、その頂点から最も遠い頂点を見つけ、新しい頂点から最も遠い頂点を見つけます。そして、ピークのペアが互いに最も遠くなるまで続けます。
頂点のペアB1とB2を取得しました。 上記のように、ペアに対してベクトルMを見つけます。 min（M（i））が見つかった行は、中心の候補です。Aで示します。列Aの値min（M（i））が最大の場合、中心と半径は既に見つかりました。 そうでない場合、列Aの最大値は別の頂点までの距離に対応します（B1でもB2でもありません）。 したがって、リストに新しい頂点B3を取得して、ベクトルMを検索します。また、B3の最も遠い頂点を検索し、B1またはB2でない場合はB4として追加することもできます。 したがって、中心と半径が見つかるまで、頂点Bのリストを増やします。
より厳密には、アルゴリズムと必要な証拠を使用して、このアルゴリズムはで説明されており、米国の道路網のいくつかのグラフでの使用結果も示しています。linkおよびlinkではあまり学術的ではありませんが、より明確に説明されています。
問題2.最短距離のマトリックスを検索する
最も一般的なFCD検索アルゴリズム（たとえば、Floyd-Worshell）をここで説明します 。 それらはすべて普遍的であり、そのうちの1つ（バイナリヒープを備えたダイクストラアルゴリズム）は、スパースグラフなどの概念を考慮に入れています。 ただし、彼は道路網の機能も使用していません。
これらを完全に異なるアルゴリズムで使用し、既存のグラフでは、ダイクストラのアルゴリズムと比較して数十倍の加速が得られます。 このアルゴリズムの特徴は、MKPを検索することであり、すぐにすべてが正確である（つまり、おおよそではなく、発見的ではない）ことです。
アルゴリズムの基本的な考え方を検討してください。 その本質は、残りのポイントの最短距離を変更せずにグラフの頂点を削除することです。 これを行うと、リモート頂点がどのポイントでどの距離でアタッチされたかを覚えて、1つを除くすべてのポイントを削除し、それらをグラフに戻しますが、距離はすでに計算されています。
簡単なものから始めましょう。上から1次です。どんな場合でも削除できます。 頂点自体へのパスを除き、最短パスはそれを通過せず、削除された頂点がアタッチされた頂点を正確に通過します。
Aを次数2の頂点とし、頂点B1およびB2にアタッチします。 ルートB1-A-B2がエッジB1-B2より長いか等しい場合、ポイントA自体へのルートを除いて、ルートはポイントAを通過しません（他のすべてはB1-B2を通過します）。 したがって、ポイントAは削除できます。 それ以外の場合、つまり B1-A-B2がB1-B2より短い場合、またはエッジB1-B2がまったくない場合、エッジB1-B2の重みを重みの合計に等しく設定することにより、頂点Aを削除できます：| B1-A | + | A-B2 |。 Aから他のポイントへのルートは、B1またはB2のいずれかを通過します。B1とB2の距離がわかっている場合、Aからの距離も簡単に計算できます。
同じ原理で、必要に応じてBi-A-BjをBi-Bjに置き換えて、任意の角度で頂点を削除できます。 確かに、頂点の次数が大きいほど、より多くのエッジをチェックする必要があることを理解する必要があります。 次数nの頂点の場合、この数はn（n-1）/ 2です。
理論的には、この方法で任意のグラフのすべての頂点を削除できますが、一般的な場合、エッジの数の増加に問題があります。 次数nの頂点を削除すると、削除された頂点に隣接する頂点の次数は次のようになります：-1ではなく減少、n-2では増加。 次数3以上の頂点を削除すると、残りの頂点の次数が一般的に大きくなり、グラフはますますまばらになり、最終的に、頂点の削除はかなり時間がかかるタスクになります。 一般的な場合、アルゴリズムは非常に面倒で実用的ではありませんが、これはまさに一般的な場合です。
道路ネットワークのグラフには、この種のユニークな特徴があります。多くのピークは、成長することなく除去できるだけでなく、隣接するピークの程度を減少させることもできます。 さらに、一部の頂点を今すぐ「正常に」削除できない場合は、隣接するいくつかの頂点を削除した後、「正常に」削除できます。
したがって、各ステップで、より「正常に」削除された頂点から開始して、削除する正しい頂点を選択する必要があります。
ここでより詳細にアルゴリズム自体を見ることができます 。 残りの頂点間の距離とパスを維持しながら、頂点を削除する方法について説明します。 このプロセスは逆アセンブリと呼ばれます。 後でグラフを復元し、頂点を一度に1つずつ逆の順序で追加する方法と、MKPを再計算する方法について説明します。 このプロセスはアセンブリと呼ばれます。
また、米国の道路網のグラフでアルゴリズムを使用した結果も示されています。
おわりに
道路網を一般的なグラフとしてではなく、いくつかの特別な特性を持つグラフとして考えると、多くの実際的な問題に対してより効率的なアルゴリズムを作成して正常に適用できます。