Floyd-Warshal アルゴリズムを使用して、任意の 2 つのノード間の最短パスを検索します。

C コードまたは期待値として定義されるマクロがあり、ユーザーが必要とするたびに再利用されます。フロイド・ウォルシャル アルゴリズムは、指定された重み付きグラフ内の頂点のすべてのペア間の最短経路を見つけるプロセスです。このアルゴリズムは動的プログラミング アプローチに従って、最小重みグラフを見つけます。

フロイト・ワルシャルアルゴリズムの意味を図で理解しましょう -

頂点 1 をソース、頂点 4 を目的地として、それらの間の最短パスを見つけます。

ターゲット頂点 4 に接続できるパスが 2 つあることがわかりました。

• 1 -> 4 – エッジの重みは 5

• 1 -> 8 -> 3 -> 4 – エッジの重み (1 2 1) は 4 です。

与えられたグラフ I では、2 つの頂点を接続する最小のエッジが表示されます。ここで、頂点 8 と頂点 3 の間のパスは、頂点 1 と頂点 4 を接続し、エッジは 4## になります。 ＃。一方、頂点 1 と頂点 4 の間には有向辺があり、辺の重みは 5 です。

次に、2 つの重み、つまり

4 と 5 を比較します。したがって、ここでの 4 は、Floyd Warshall アルゴリズムに従って計算されたグラフの最小重みです。

この記事では、Floyd Warshall アルゴリズムを使用して、任意の 2 つのノード間の最短パスを見つけます。

＃＃＃文法＃＃＃

プログラムでは次の構文が使用されます -

リーリー

パラメータ

data_type[][]

- ユーザーが指定したデータ型。最初の配列は行を表し、2 番目の配列は列を表します。したがって、これは 2 次元配列を表します。

array_name

- 配列に付けられた名前。

＃＃＃アルゴリズム＃＃＃

ヘッダー ファイル

'iostream'

でプログラムを開始し、マクロの位置を

'INF'
• (無限大) として定義します。これは、後で 2 つの条件を満たすためです。次元配列行列と if-else ステートメント。

  次に、'printPath'

  という名前のグローバル関数定義を作成し、3 つのパラメーター、つまり
'parent[]'、'i'
• 、および

  を受け入れます。 j' パスが存在することを確認します。 次に、main 関数を開始し、頂点の数を表す値 ‘4’

  を変数
‘V’
• に保存します。次に、値を隣接行列の形式で変数

  'dist[V][V]' に保存します。ご存知のとおり、dist[i][j] は 2D 行列を表し、'i' から 'j' までのエッジの重みを定義します。隣接行列を保存します。 次に、変数 'parent'

  の 2D 配列を初期化しています。サイズは
[V][V]
• です。

  この変数では、頂点の各ペア 'i' と

  'j'
w.r.t

'parent[i][j]' を表示するために使用します。 ネストされた 2 つの for ループを使用して、最短パスを見つけます。最初の for ループは、行列内の行を反復処理します。次に、2 番目の for ループを通じて行列内の列を反復処理し、if-else ステートメント -

を使用して次の条件を確認します。

• If (dist[i][j] != INF && i != j) { parent[i][j] = i;}

  の中国語訳は次のとおりです:parent[i][j] = i;}
if ステートメントでは、
• 'and' (&&)

  演算子を使用して 2 つの条件を表現します。両方の条件が満たされた場合、'i' は 'parent[i ][j] に格納されます。 ]' を実行し、パスが存在することを確認します。

  ＃＃＃＃＃＃＃＃＃他の{ parent[i][j] = -1;} の中国語訳は次のとおりです:parent[i][j] = -1;}

  else ステートメントでは、パスが存在しないことを確認するために、「-1」を "parent[i][j]"

  に初期化します。

• 次に、3 つのネストされた

  for ループから開始し、0 ～ V-1 の範囲にある k 個の頂点を適用します。この範囲を利用して、最短距離とパスが更新されます。 3 番目のネストされたループでは、

のような次の条件を使用します。 リーリー
• ここで、K は 2 次元配列行列の行部分と列部分を更新し、新しく更新された最短経路と距離を検証します。

  次に、次の条件を与えて、すべての頂点ペアの最短距離とパスを出力します。

ネストされた 2 つの for ループを使用して、最短距離とパスを出力します。

• 2 番目の for ループの下で if ステートメントを使用して、dist[i][j] が無限大に等しいかどうかを確認します。無限大であることが判明した場合は「INF」を出力し、それ以外の場合は最短パスを出力します。

最後に、3 つのパラメータ (parent[i]、i、j) を渡して、
• 'printPath()'

  という名前の関数を呼び出します。

＃＃＃例＃＃＃ このプログラムでは、Floyd Warshall アルゴリズムを使用して、任意の 2 つのノード間の最短パスを計算します。

• #include <iostream> 
  using namespace std; 
  #define INF 1000000000 // Infinity
  
  void printPath(int parent[], int i, int j) {
     if (i == j) 
        cout << i << " "; 
     else if (parent[j] == -1) 
       cout << "No path exists"; 
     else
     { 
        printPath(parent, i, parent[j]); 
        cout << j << " "; 
     }
  } 
  
  int main() 
  {
     int V = 4; 
     // V represent number of vertices
     int dist[V][V] = {{0, 2, INF, 4}, 
        {6, 0, 5, 3}, 
        {INF, 10, 0, 1}, 
        {7, 9, 8, 0}}; 
     // Represent the graph using adjacency matrix
  
     // Apply the Floyd Warshall algorithm to find the shortest paths
     int parent[V][V];
     for (int i = 0; i < V; i++) 
     { 
        for (int j = 0; j < V; j++) 
        {
           if (dist[i][j] != INF && i != j)
           parent[i][j] = i;
           else
           parent[i][j] = -1;
        }
     }
     // update the path and distance using the k vertex range from 0 to V-1.
     for (int k = 0; k < V; k++) 
     { 
        for (int i = 0; i < V; i++) 
        { 
           for (int j = 0; j < V; j++) 
           { 
              if (dist[i][j] > dist[i][k] + dist[k][j]) 
              {
                 dist[i][j] = dist[i][k] + dist[k][j];
                 parent[i][j] = parent[k][j];	
              }
           }
        }
     }
  
     // Print shortest distances and paths between all pairs of vertices
     for (int i = 0; i < V; i++) 
     { 
        for (int j = 0; j < V; j++) 
        { 
           cout << "The Shortest distance between " << i << " and " << j << " is ";
           if (dist[i][j] == INF) 
              cout << "INF "; 
           else
              cout << dist[i][j] << " ";
  
           cout << "and the shortest path is:- ";
           printPath(parent[i], i, j);
           cout << endl;
        } 
     } 
  
     return 0; 
  }
  

  输出

  The Shortest distance between 0 and 0 is 0 and the shortest path is:- 0 
  The Shortest distance between 0 and 1 is 2 and the shortest path is:- 0 1 
  The Shortest distance between 0 and 2 is 7 and the shortest path is:- 0 1 2 
  The Shortest distance between 0 and 3 is 4 and the shortest path is:- 0 3 
  The Shortest distance between 1 and 0 is 6 and the shortest path is:- 1 0 
  The Shortest distance between 1 and 1 is 0 and the shortest path is:- 1 
  The Shortest distance between 1 and 2 is 5 and the shortest path is:- 1 2 
  The Shortest distance between 1 and 3 is 3 and the shortest path is:- 1 3 
  The Shortest distance between 2 and 0 is 8 and the shortest path is:- 2 3 0 
  The Shortest distance between 2 and 1 is 10 and the shortest path is:- 2 1 
  The Shortest distance between 2 and 2 is 0 and the shortest path is:- 2 
  The Shortest distance between 2 and 3 is 1 and the shortest path is:- 2 3 
  The Shortest distance between 3 and 0 is 7 and the shortest path is:- 3 0 
  The Shortest distance between 3 and 1 is 9 and the shortest path is:- 3 1 
  The Shortest distance between 3 and 2 is 8 and the shortest path is:- 3 2 
  The Shortest distance between 3 and 3 is 0 and the shortest path is:- 3 
  

  结论

  我们学习了使用Floyd Warshall算法找到任意两个节点之间的最短路径的概念。我们使用邻接矩阵作为程序的输入，通过它我们找到了最短路径和距离。此外，为了更新路径和距离，我们使用了k个顶点来更新行和列。在我们的日常生活中，我们在谷歌地图上搜索最短路线或路径，从一个起点到目的地。

以上がFloyd-Warshal アルゴリズムを使用して、任意の 2 つのノード間の最短パスを検索します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。