Floyd/Warshallアルゴリズム最長のパスで最も安いパスを見つけるmod

Question

私はFloydのアルゴリズムを編集しているので、各Dkの代わりにkが最も高い中間頂点であり、kは最大のパス長です。最終的にはFloydと同じ出力を持ちますが、すべてのサブタイトルは異なる可能性があります。たとえば、4つの頂点：0,1,2,3がある場合、私は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 

私はフロイドのアルゴリズムとは別に、この中に実装を理解する助けと場所を開始することを確認していない必要があります。ここで

Answer 1

は、あなたの問題のためのサンプル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; 
 
}