日本語
日本語
グラフ理論では、最短経路の問題は、指示されたグラフまたは無向グラフの2つの頂点間の最短パスを見つけることを含む古典的なアルゴリズム問題です。 Floyd-Warshallアルゴリズムは、この問題を解決するために使用される古典的な動的プログラミングアルゴリズムです。この記事では、PHPを使用してFloyd-Warshallアルゴリズムを実装する方法について詳しく説明します。
Floyd-Warshallアルゴリズムは、グラフ内のすべての頂点間の最短パス長を繰り返し比較することにより、最短のパス問題を解決するアルゴリズムです。 2次元配列を使用して、頂点間の最短パス長を保存し、各反復でこの配列を更新します。最後に、すべての頂点間の最短パスを取得できます。
まず、n x nの2D配列を作成する必要があります。ここで、nはグラフ内の頂点の数を表します。配列内の各要素は、2つの頂点間の距離を表し、2つの頂点の間にエッジがない場合、距離は無限に設定されます。以下は、PHPコードの実装です。
関数flydwarshall（$ graph）{
$ n = count（$ graph）;
$ dist = $ graph;
for（$ k = 0; $ k <$ n; $ k ++）{
for（$ i = 0; $ i <$ n; $ i ++）{
for（$ j = 0; $ j <$ n; $ j ++）{
if（$ dist [$ i] [$ k] + $ dist [$ k] [$ j] <$ dist [$ i] [$ j]）{
$ dist [$ i] [$ j] = $ dist [$ i] [$ k] + $ dist [$ k] [$ j];
}
}
}
}
$ distを戻るします。
}
次に、グラフの例を定義し、アルゴリズムをテストします。隣接するマトリックスを使用してグラフの構造を表し、2次元配列に頂点間の距離を保存します。サンプルコードは次のとおりです。
$ graph = [
[0、5、inf、10]、
[inf、0、3、inf]、
[inf、inf、0、1]、
[inf、inf、inf、0]
];
上記の図の例では、INFは2つの頂点の間にエッジがないことを意味し、その距離を非常に大きな値に設定します。これで、Floydwarshall関数を呼び出して、最短パスアレイを計算できます。
$ result = floydwarshall（$ graph）;
上記のコードを実行すると、次の結果が得られます。
0 5 8 9 INF 0 3 4 inf inf 0 1 inf inf inf inf 0
上記の結果は、図のすべての頂点間の最も短い経路長を示しています。 INFとは、2つの頂点間にパス接続がないことを意味します。
この記事では、PHPを使用してFloyd-Warshallアルゴリズムを実装して、グラフの最短経路問題を解決する方法を紹介します。動的プログラミングのアイデアを使用することにより、O（n^3）の時間の複雑さでグラフ内のすべての頂点間の最短パス長を見つけることができます。アルゴリズムの設計手法を合理的に使用することにより、このアルゴリズムを実用的な問題を解決する際に迅速かつ効率的に適用できます。
