フロイト(Floyd)アルゴリズムの個人的な理解
Floydアルゴリズムも有名な最短経路の解法アルゴリズムであり、その過程は非常に簡潔で優雅であり、基本原理はDijkstraアルゴリズムと似ている.2つのアルゴリズムの時間複雑度を比較すると、Dijkstraアルゴリズムの効率はより高くなります.Floydアルゴリズムの時間複雑度はO(n^3)であり、DijkstraアルゴリズムはO(n^2)の時間複雑度だけが必要です.しかし、Floydアルゴリズムの利点は、任意の2つのノード間の最短経路を一度に求めることができ、Dijkstraアルゴリズムは、特定のノードで開始する最短経路のみを求めることができることである.
Flooydのアルゴリズムの実現コードを直接提供します.このアルゴリズムの具体的なステップを理して、自分の理解を話します.
なぜこのような規則によって更新されて、各ノード間の最短経路が見出されるのでしょうか?ここで例を挙げて説明すれば、この問題をはっきり説明できるはずです.ノードV 2からV 5までの最短経路は、V 2→V 4→V 9→V 7→V 5と予め知っていたと仮定します.
第一のステップは、初期化プロセスにおいて、(*D)[2][9]、(*D)[9][5]、(*D)[2]、[5]および(*P)[2]、[9]、(*P)[9]、[5]、(**P)[2][5]の初期値を獲得した.
第二のステップは、Floydアルゴリズムに従って反復して、kが4に等しい場合、V 2とV 9の間にV 4を挿入した後、V 2とV 9の間の経路長は史上最低に達し、(*D)[2][9]は(*D)[2]+(*D)[4]、[9],(*P)[2]は4]に更新された.その後の反復において、より短いパスは発生しないので、(*D)[2][9]、[2]、[9]はその後の反復において変更されない.
第3ステップは、繰り返してkが7に等しい場合、V 9とV 5の間の経路長は史上最低となり、(*D)[9][5]は(*D)[9]+(*D)[7]+[5],(*P)[9][5]は7に更新され、その後は変更されない.
第4ステップは、繰り返してkが9に等しい場合、V 2とV 5の間の経路長は史上最低点に達し、(*D)[2][5]は(*D)[2]+(*D)[9]+[5],(*P)[2][5]は9に更新され、その後は変更されない.このようにしてV 2とV 5の間の最短経路が見つかった.
V 2とV 5の間の最短経路の長さを算出しましたが、どうやってこの経路の軌跡を見つけますか?実は***Pから推測します.上記の例を例にとって、V 2とV 5の間の最短経路の軌跡を印刷したい場合.まず、(＊P)[2][5]=9を知っています.軌跡はV 2→V 9→V 5です.(*P)[2][9]=4かつ(*P)[9][5]=7に基づいて、軌跡はV 2→V 4→V 9→V 7→V 5となる.(*P)[2][4]=2,(*P)[4]=4,(*P)[9]=9,(*P)[7]=7,(*P)[5]=7により、新たなノードが追加されていないことが確認できますので、最終的な軌跡はV 2→V 4→V 9→V 7→V 5と確定します.
Flooydのアルゴリズムの実現コードを直接提供します.このアルゴリズムの具体的なステップを理して、自分の理解を話します.
#define MAXVEX 15
#define INFINITY 65535
typedef int Pathmatrix[MAXVEX][MAXVEX]; //
typedef int ShortPathTable[MAXVEX][MAXVEX]; //
void ShortestPath_Floyd(MGraph G, Pathmatrix *P, ShortPathTable *D)
{
int v, w, k;
//
for(v = 0; v < G.numVertexes; v++)
{
for(w=0; w < G.numVertexes; w++)
{
(*D)[v][w] = G.matrix[v][w];
(*P)[v][w] = w;
}
}
//Floyd
for(k = 0; k < G.numVertexes; k++)
{
for(v = 0; v < G.numVertexes; v++)
{
for(w = 0; w < G.numVertexes; w++)
{
if((*D)[v][w] > (*D)[v][k] + (*D)[k][w])
{
(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
(*P)[v][w] = k;
}
}
}
}
}なぜこのような規則によって更新されて、各ノード間の最短経路が見出されるのでしょうか?ここで例を挙げて説明すれば、この問題をはっきり説明できるはずです.ノードV 2からV 5までの最短経路は、V 2→V 4→V 9→V 7→V 5と予め知っていたと仮定します.
第一のステップは、初期化プロセスにおいて、(*D)[2][9]、(*D)[9][5]、(*D)[2]、[5]および(*P)[2]、[9]、(*P)[9]、[5]、(**P)[2][5]の初期値を獲得した.
第二のステップは、Floydアルゴリズムに従って反復して、kが4に等しい場合、V 2とV 9の間にV 4を挿入した後、V 2とV 9の間の経路長は史上最低に達し、(*D)[2][9]は(*D)[2]+(*D)[4]、[9],(*P)[2]は4]に更新された.その後の反復において、より短いパスは発生しないので、(*D)[2][9]、[2]、[9]はその後の反復において変更されない.
第3ステップは、繰り返してkが7に等しい場合、V 9とV 5の間の経路長は史上最低となり、(*D)[9][5]は(*D)[9]+(*D)[7]+[5],(*P)[9][5]は7に更新され、その後は変更されない.
第4ステップは、繰り返してkが9に等しい場合、V 2とV 5の間の経路長は史上最低点に達し、(*D)[2][5]は(*D)[2]+(*D)[9]+[5],(*P)[2][5]は9に更新され、その後は変更されない.このようにしてV 2とV 5の間の最短経路が見つかった.
V 2とV 5の間の最短経路の長さを算出しましたが、どうやってこの経路の軌跡を見つけますか?実は***Pから推測します.上記の例を例にとって、V 2とV 5の間の最短経路の軌跡を印刷したい場合.まず、(＊P)[2][5]=9を知っています.軌跡はV 2→V 9→V 5です.(*P)[2][9]=4かつ(*P)[9][5]=7に基づいて、軌跡はV 2→V 4→V 9→V 7→V 5となる.(*P)[2][4]=2,(*P)[4]=4,(*P)[9]=9,(*P)[7]=7,(*P)[5]=7により、新たなノードが追加されていないことが確認できますので、最終的な軌跡はV 2→V 4→V 9→V 7→V 5と確定します.