フロイドアルゴリズム研究ノート

アルゴリズムのアイデア

パス行列

重み行列を通じてグラフの各 2 点間の最短パス行列を見つけます。グラフの重み付き隣接行列 A=[a(i,j)] n×n から開始して、式に従って、行列 D(0)=A から n 回の更新を再帰的に実行します。行列 D( 1) が構築されます。次に、同じ式を使用して D(1) から D(2) を構築します。最後に、同じ式を使用して、D(n-1) から行列 D(n) を構築します。行列 D(n) の行 i と列 j の要素は、頂点 i から頂点 j までの最短のパス長です。同時に、後続ノードの行列パスと呼ばれます。 2 点間の距離を記録するためにも導入されます。

状態遷移方程式

状態遷移方程式は次のとおりです。map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}; ,j ] は i から j までの最短距離を表し、K は網羅的な i, j のブレークポイントであり、map[n,n] の初期値は 0 である必要があります。

もちろん、この道路がアクセスできない場合は、特別な処理を行う必要があります。たとえば、map[i,k] 道路がありません。

コアアルゴリズム

1、任意の一方的なパスから開始します。すべての 2 点間の距離がエッジの重みになります。2 点を接続するエッジがない場合、重みは無限大になります。

2. 頂点 u と v の各ペアについて、u から w への経路が既知の経路よりも短い頂点 w があるかどうかを確認します。その場合は更新してください。

グラフを隣接行列 G として表します。Vi から Vj へのパスがある場合、G[i,j]=d、d はパスの長さを表し、そうでない場合は G[i,j]=無限大を表します。挿入された点の情報を記録する行列 D を定義します。D[i,j] は、Vi から Vj に渡す必要がある点を表します。D[i,j]=j を初期化します。各頂点をグラフに挿入し、挿入点の後の距離を元の距離 G[i,j] = min(G[i,j], G[i,k]+G[k,j]) と比較します。 G[i,j]の値が小さくなると、D[i,j]=kになります。 G には 2 点間の最短道路の情報が含まれ、D には最短経路の情報が含まれます。

時間計算量と空間計算量

時間計算量:コアアルゴリズムは緩和法を使用した3つのforループであるため、時間計算量はO(n^3)です

空間計算量:全体のアルゴリズムの空間消費量はn*n 行列なので、空間計算量は O(n^2) です

C++ コード

// floyd.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include"iostream"
#include"fstream"
#define maxlen 20
#define maximum 100
using namespace std;

typedef struct graph
{
 int vertex;
 int edge;
 int matrix[maxlen][maxlen];
};
int _tmain(int argc, _TCHAR* argv[])
{
 ofstream outwrite;
 outwrite.open("h.txt",ios::app|ios::out);
 outwrite<<"welcome to the graph world!\n";
 outwrite<<"the initial matrix is:\n";
 int vertexnumber;
 int edgenumber;
 int beginning,ending,weight;
 int mindistance[maxlen][maxlen];
 int interval[maxlen][maxlen];
 graph floydgraph;
 cout<<"welcome to the graph world!"<<endl;
 cout<<"input the number of the vertex: ";
 cin>>vertexnumber;
 cout<<"input the number of the edge: ";
 cin>>edgenumber;
 for (int i = 0; i < vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   floydgraph.matrix[i][j]=maximum;
  }
 }
 for (int i = 0; i <edgenumber; i++)
 {
  cout<<"please input the beginning index: ";
  cin>>beginning;
  cout<<"please input the ending index: ";
  cin>>ending;
  cout<<"please input the distance of the two dot: ";
  cin>>weight;
  floydgraph.matrix[beginning][ending]=weight;
 }
 for (int i = 0; i <vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   mindistance[i][j]=floydgraph.matrix[i][j];
   outwrite<<floydgraph.matrix[i][j]<<"\t";
   interval[i][j]=-1;
  }
  outwrite<<"\n";
 }
 for (int k = 0; k <vertexnumber; k++)
 {
  for (int i = 0; i < vertexnumber; i++)
  {
   for (int j = 0; j < vertexnumber; j++)
   {
    if(mindistance[i][j]>mindistance[i][k]+mindistance[k][j])
    {
     mindistance[i][j]=mindistance[i][k]+mindistance[k][j];
     interval[i][j]=k;
    }
   }
  }
 }
 outwrite<<"\n"<<"after the floyd transition, the matrix is: "<<"\n";
 for (int i = 0; i < vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   cout<<"the mindistance between "<<i<<"  and  "<<j <<" is: ";
   cout<<mindistance[i][j]<<endl;
   cout<<"the two points pass through the point: "<<interval[i][j];
   cout<<endl;
   outwrite<<mindistance[i][j]<<"\t";
  }
  outwrite<<"\n";
 }
 outwrite<<"\n";
 outwrite<<"the points between the beginning point and the ending point is:"<<"\n";
 for (int i = 0; i < vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   outwrite<<interval[i][j]<<"\t";
  }
  outwrite<<"\n";
 }
 outwrite.close();
 getchar();
 getchar();
 getchar();
 return 0;
}