1. 概要

このチュートリアルでは、 Floyd-Warshallアルゴリズムについて説明し、次にその時間計算量を分析します。

2. フロイド-ウォーシャルアルゴリズム

Floyd-Warshallアルゴリズムは、重み付けされた有向グラフの各頂点ペアの最短経路を見つけるための一般的なアルゴリズムです。

すべてのペアの最短経路問題では、グラフ内の各頂点から他のすべての頂点へのすべての最短経路を見つける必要があります。

それでは、アルゴリズムに飛び込みましょう。

入力として有向加重グラフを使用しています。 そして最初に、与えられたグラフからグラフ行列を作成します。この行列には、グラフのエッジの重みが含まれます。

次に、マトリックスの対角位置にを挿入します。残りの位置には、入力グラフのそれぞれのエッジの重みが入力されます。

次に、2つの頂点間の距離を見つける必要があります。 距離を見つける際に、選択した2つの頂点の間に中間頂点があるかどうかも確認します。 中間頂点が存在する場合は、この中間頂点を通過する、選択した頂点のペア間の距離を確認します。

中間頂点を通過するときのこの距離が、中間頂点を通過せずに選択された2つの頂点間の距離よりも小さい場合、マトリックス内の最短距離値を更新します。

反復回数は、頂点セットのカーディナリティに等しくなります。アルゴリズムは、指定されたグラフの各頂点から別の頂点までの最短距離を返します。

3. 例

重み付き有向グラフでFloyd-Warshallアルゴリズムを実行してみましょう。

まず、入力グラフからグラフ行列を作成します。 次に、マトリックスの対角位置に挿入します。残りの位置には、入力グラフのエッジの重みが入力されます。

   

これで、反復を開始する準備が整いました。 頂点セットのカーディナリティはです。 ループ時間を繰り返します。

最初のループから始めましょう。 最初のループk= 1、i = 1、j = 1 では、行列を更新する必要があるかどうかを確認します。

> >

ループ値が条件を満たさないため、マトリックスは更新されません。

続けて、値 k = 1、i = 1、j = 2 について、もう一度確認してみましょう。

> >

したがって、マトリックスに変更はありません。 このようにして、続けてすべての頂点のペアをチェックします。

距離条件を満たすいくつかの値に早送りしましょう。

ループ値k= 1、i = 2、j = 3 の場合、条件が満たされていることがわかります。

> > >

そのため、新しい距離を計算します。

したがって、条件は頂点ペアに対して満たされます。 最初は、頂点からまでの距離はでした。 ただし、ここで新しい最短距離が見つかりました。 そのため、この新しい最短経路距離で行列を更新します。

   

ループ値がアルゴリズムで指定された距離条件を満たすように、3つのネストされたループの別の値のセットを取得しましょう。 k = 2、i = 4、j = 1 ：

> > >

条件が満たされると、新しい距離計算が計算されます。

したがって、マトリックスを次の新しい値で更新します。

   

同様に、続行してさまざまなループ値をチェックします。 最後に、アルゴリズムが終了した後、すべてのペアの最短距離を含む出力行列を取得します。

   

4. 時間計算量分析

まず、エッジの重みをマトリックスに挿入しました。 これは、グラフのすべての頂点にアクセスするforループを使用して行います。 これは時間内に実行できます。

次に、3つのネストされたループがあり、それぞれが1からグラフ内の頂点の総数になります。 したがって、このアルゴリズムの合計時間計算量はです。

5. 結論

要約すると、このチュートリアルでは、重み付き有向グラフですべてのペアの最短距離を見つけるためのFloyd-Warshallアルゴリズムについて説明しました。

さらに、アルゴリズムの例と時間計算量分析も示しました。