1. 概要

このチュートリアルでは、グラフの直径を見つける問題について説明します。 問題が何であるかを説明することから始め、次にそれを解決するためのアルゴリズムに移ります。 最後に、1つのアルゴリズムの擬似コードを提供し、その時間計算量を分析します。

2. 問題の説明

グラフの直径は、グラフ内の最大最短経路距離として定義されます。 つまり、これはすべてのペアの最大値です。ここで、は頂点から頂点までの最短経路距離を示します。

または、頂点の偏心によって直径を定義することもできます。 で示される頂点の離心率は、他の頂点からの最大最短経路距離に等しくなります。 次に、直径はすべての頂点の偏心の最大値として定義できます。

入力グラフが交通機関または道路網を表す場合、直径を計算することで、最悪の場合に車両がある地点から別の地点まで移動する必要がある距離を知ることができます。 もちろん、これは、車両が常にポイントからポイントへの最短経路をたどることができることを前提としています。

ここでは、無向グラフ（直径は赤でマークされています）で直径の概念を説明します。

上のグラフの直径を計算してみましょう。 最短経路距離については、、、、、、、、、、、、、およびがあります。 したがって、これらの値の最大値であるため、直径はに等しくなります。

3. アルゴリズム

このセクションで紹介するアルゴリズムの高レベルの戦略は、これまでに見られた最大値を追跡しながら、すべての最短経路を計算することです。 そして最後に、最終的な最大値を直径として返します。

入力グラフが非負のエッジ重みを持つ加重有向グラフである場合はどうなりますか？ 私たちが取ることができる1つのアプローチは、すべての頂点からダイクストラのアルゴリズムを実行し、最大の最短経路距離を追跡することです。

より良いアプローチは、Floyd-Warshallアルゴリズムなどの最適な全ペア最短経路アルゴリズムを実行することです。 このアプローチの利点は、使用するスペースが少なく、実装が簡単なことです。 さらに、グラフに負のエッジの重みが存在する場合でも機能しますが、Dijkstraアプローチは非負のエッジの重みでのみ機能します。 このFloyd-Warshall法は、入力グラフに負のサイクルがない場合にのみ使用できることに注意してください。

グラフが無向の重み付けされていないグラフである場合、いくつかのオプションがあります。 1つのオプションは、すべての頂点から幅優先探索を実行し、最大最短経路距離を追跡することです。 もう1つのオプションは、最初にグラフをすべてのエッジの重みが1に等しい有向グラフに変換してから、上記のFloyd-Warshallアプローチを使用することです。

4. 擬似コード

それでは、負のサイクルのない重み付き有向グラフでのFloyd-Warshallアプローチの擬似コードを見てみましょう。

 

 

上記のアルゴリズムは、負のサイクルのない重み付き有向グラフを表すby行列を入力として受け取り、その直径を出力します。 この行列のエントリ、、は次のようになります。

  • 等しい場合はゼロ
  • 等しくなく存在する場合の有向エッジの重み、および
  • 等しくなく、存在しない場合は無限大

アルゴリズムの最初の部分は、Floyd-Warshallアルゴリズムと同じです。 ノードのすべてのペア間の最短経路の値を格納する行列を定義します。

より正確には、このマトリックスは、ノードからノードへの最短パスの長さを表す値を格納します。このパスは、セット内の頂点のみを中間頂点として使用します。 次に、マトリックスの値を入力するためのボトムアップ動的計画法手順である三重にネストされたループがあります。

すべての最短経路値を計算したら、すべてのペアを反復処理し、これまでの最大値を追跡することにより、すべての中で最大値を計算します。 この値は、直径として返されます。



5. 複雑さの分析


グラフの直径を計算するためにどのアプローチを採用しても、常に最悪の場合の複雑さになります。ここで、はグラフ内のノードの数です。


これには、Floyd-Warshall法が含まれます。 Floyd-Warshallアプローチでは、最初に、時間がかかる定数時間演算を使用して、トリプルネストされたforループを作成します。 次に、時間がかかる二重ネストされたforループがあります。 が支配的であるため、全体的な時間計算量はです。


6. 結論


この記事では、グラフの直径を時間内に計算できることを確認しました。ここで、はグラフ内のノードの数に等しくなります。


また、Floyd-Warshallアプローチの擬似コードを確認し、その時間計算量を分析しました。