matrix - Floyd/Warshall 算法 mod 找到最大长度 k 的最便宜路径

Question

我正在编辑 Floyd 算法，因此 k 是最大路径长度，而不是每个 Dk(其中 k 是最高中间顶点)。最终它将具有与 Floyd 相同的输出，但每次迭代都可能不同。例如，如果有 4 个顶点:0,1,2,3，我想找到从 0 到 3 的最便宜路径，其最大长度为 K。假设该图是有向的。

因此，如果 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;
}