4

私はフロイドのアルゴリズムを編集しているので、k が最高の中間頂点である各 Dk の代わりに、k が最大パス長です。最終的にはフロイドのものと同じ出力になりますが、すべてのサブイテレーションは異なる可能性があります。たとえば、0、1、2、3 の 4 つの頂点がある場合、最大長が K である 0 から 3 までの最も安価なパスを見つけたいとします。グラフは有向であると想定されます。

したがって、k=2 の場合、すべての矢印がエッジ/パスを示す 0->3...0->1->3...0->2->3 しかチェックできません。k=3 の場合、0->3...0->1->3...0->1->2->3...0->2->3... しかチェックできません。 0->2->1->3 など...

    0   1   2   3
0   0   4   9   12
1   9   0   3   11   // the adj matrix I'm referencing for 1 example
2   9   10  0   2
3   1   99  6   0

これの実装を理解するのに助けが必要で、フロイドのアルゴリズムは別として、どこから始めればよいかわかりません。

4

1 に答える 1

0

問題のサンプル C++ コードを次に示します。

#define INF 100000005

using namespace std;

int main()
{
   int i,j,k,n,m,ver,edg,len,from,to;
   int mat[10][10][10],next[10][10][10];
   cin>>ver;
   for(i=0;i<ver;i++)
   {
       for(j=0;j<ver;j++)
       {
           for(k=0;k<ver;k++)
            {
                mat[i][j][k]=INF;
                next[i][j][k]=j;
            }
       }
   }
   for(i=0;i<ver;i++)
   {

       for(j=0;j<ver;j++)
       {
           cin>>mat[i][j][1];
       }
   }
   for(len=2;len<ver;len++)
   {
       for(k=0;k<ver;k++)
       {
           for(i=0;i<ver;i++)
           {
               for(j=0;j<ver;j++)
               {
                   if(mat[i][k][len-1]+mat[k][j][1]<mat[i][j][len])
                   {
                       mat[i][j][len]=mat[i][k][len-1]+mat[k][j][1];
                       next[i][j][len]=next[i][k][len-1];
                   }
               }
           }
       }
   }
   if(mat[0][3][3]!=INF)
   {
       cout<<"Minimum Cost from 0 to 3,using exactly 3 pathlen is: "<<mat[0][3][3]<<endl;
       from=0;
       to=3;
       len=3;
       cout<<from;
       while(from!=to)
       {
           from=next[from][to][len--];
           cout<<"-->"<<from;
       }
   }
   else
       cout<<"No path"<<endl;
}

于 2015-05-24T14:00:51.423 に答える