flodフロイドアルゴリズムの詳細
フロイドアルゴリズムの概要:
頂点ペア間の最短経路とは、与えられた有向網G=(V,E)について、Gのいずれかのペアの頂点に対してV,W(V≠W)を秩序化し、VからWまでの最短距離とWからVまでの最短距離を探し出すことである.
この問題を解決する有効な方法は、各頂点をソース点として順番にディジェストラアルゴリズムをn回繰り返し実行することで、各対の頂点間の最短経路を求めることができ、総時間複雑度はO(n 3)である.
フロイド(Floyd)は,時間的複雑さもO(n 3)であるが,そのアルゴリズムの形式はより簡単で,理解とプログラミングが容易である,図中の任意の2つの頂点間の最短経路を求める別のアルゴリズムを提案した.
アルゴリズムの基本思想
フロイドアルゴリズムは依然として図の隣接行列arcs[n+1][n+1]を用いて帯域重み有向図を記憶する.アルゴリズムの基本思想は、対角線の要素が0に等しいことを除いて、他の要素a(k)[i][j]は頂点iから頂点jまでの経路長を表し、Kは演算ステップを表すn x nのマトリクスA(k)を設定することである.開始時には、任意の2つの頂点間の有向辺の重み値を経路長とし、有向辺がない場合は経路長∞、K=0の場合はA(0)[i][j]=arcs[i][j]となり、以降は元の経路に他の頂点を中間頂点として加えることを徐々に試み、中間頂点を増やした後、得られる経路が元の経路長よりも減少した場合は、元の経路の代わりに新しい経路を用い、マトリックス要素を変更します.具体的な方法は次のとおりです.
最初のステップは、すべてのエッジに中間頂点1を加え、A[i][j]とA[i][1]+A[1][j]の小さい値をA[i][j]の値とし、完了するとA(1)を得る.
第2のステップでは、すべてのエッジに中間頂点2を加え、A[i][j]とA[i][2]+A[2][j]の小さい値をとり、完了するとA(2)…となり、このままでは、第nのステップが完了すると、A(n)が得られ、A(n)は我々が求めた結果であり、A(n)[i][j]は頂点iから頂点jまでの最短距離を表す.
頂点ペア間の最短経路とは、与えられた有向網G=(V,E)について、Gのいずれかのペアの頂点に対してV,W(V≠W)を秩序化し、VからWまでの最短距離とWからVまでの最短距離を探し出すことである.
この問題を解決する有効な方法は、各頂点をソース点として順番にディジェストラアルゴリズムをn回繰り返し実行することで、各対の頂点間の最短経路を求めることができ、総時間複雑度はO(n 3)である.
フロイド(Floyd)は,時間的複雑さもO(n 3)であるが,そのアルゴリズムの形式はより簡単で,理解とプログラミングが容易である,図中の任意の2つの頂点間の最短経路を求める別のアルゴリズムを提案した.
アルゴリズムの基本思想
フロイドアルゴリズムは依然として図の隣接行列arcs[n+1][n+1]を用いて帯域重み有向図を記憶する.アルゴリズムの基本思想は、対角線の要素が0に等しいことを除いて、他の要素a(k)[i][j]は頂点iから頂点jまでの経路長を表し、Kは演算ステップを表すn x nのマトリクスA(k)を設定することである.開始時には、任意の2つの頂点間の有向辺の重み値を経路長とし、有向辺がない場合は経路長∞、K=0の場合はA(0)[i][j]=arcs[i][j]となり、以降は元の経路に他の頂点を中間頂点として加えることを徐々に試み、中間頂点を増やした後、得られる経路が元の経路長よりも減少した場合は、元の経路の代わりに新しい経路を用い、マトリックス要素を変更します.具体的な方法は次のとおりです.
最初のステップは、すべてのエッジに中間頂点1を加え、A[i][j]とA[i][1]+A[1][j]の小さい値をA[i][j]の値とし、完了するとA(1)を得る.
第2のステップでは、すべてのエッジに中間頂点2を加え、A[i][j]とA[i][2]+A[2][j]の小さい値をとり、完了するとA(2)…となり、このままでは、第nのステップが完了すると、A(n)が得られ、A(n)は我々が求めた結果であり、A(n)[i][j]は頂点iから頂点jまでの最短距離を表す.
， ， floyd 。
void MDNet::Floyd(CDC *pDC)
{
typedef vector path;//
path p[max_vertex_num][max_vertex_num];
//p
int D[max_vertex_num][max_vertex_num];
// D
int i,j,k;
for(i=1;i<=vex_num;i++)
{//
for(j=1;j<=vex_num;j++)
{
p[i][j].push_back(i);
p[i][j].push_back(j);
// i j ij。
D[i][j]=arcs[i][j];// （i，j）
}
}
for(k=1;k<=vex_num;k++)
{//
for(i=1;i<=vex_num;i++)
{
for(j=1;j<=vex_num;j++)
{// i j k
if(i==j)continue;// （ ）
if(D[i][k]+D[k][j]