アルゴリズムのアイデア
パス行列
重み行列を通じてグラフの各 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; }