4

在解决具有n 个节点的有向加权图的最短路径问题时，是否可以修改 Floyd-Warshall 算法，使得每条最短路径的步数不超过m？更准确地说，对于每对节点i和j，您将找到从i到j的最短有向路径，其中包含不超过m个节点。时间复杂度仍然保持O ( n 3 ) 吗？

4

3 回答 3

2

同时，我发现了一个O ( n 3 log m ) 算法，用于查找具有n 个节点的图的所有对最短路径 (ASPP) 问题，这样没有路径包含超过m个节点。

给定两个n x n矩阵，比如A = [ a ij ] 和B = [ b ij ]，它们的距离积是n x n矩阵C = [ c ij ] = A x B，定义为c ij = min 1≤ k ≤ n { a ik + b kj }。

这通过以下方式与 ASPP 相关。给定图中距离的加权矩阵E ， E n是所有对最短路径的矩阵。如果我们添加约束，即没有路径包含超过m个节点，则矩阵E m是 ASPP 的解决方案。由于可以在O (log m ) 时间内找到计算能力，这为我们提供了O ( n 3 log m ) 算法。

在这里，在某些特殊情况下，人们可能会找到更快的算法来计算矩阵的距离积，但是对于我来说，微不足道的O ( n 3 ) 就足够了，因为总时间几乎与 Floyd-Warshall 方法一样快。

于 2014-05-05T11:07:04.010 回答
0

我相信这可以用不同的数据结构来完成（一个可以让你跟踪步数的数据结构）？

由于通常 Floyd-Warshall 使用连接矩阵（其中矩阵 [j][k] 表示节点 j 和 k 之间的距离）来完成，因此我们可以不将该矩阵设为整数，而是将其设为具有两个整数的结构：距离两个节点之间以及它们之间的步数。

我用 C++ 写了一些东西来解释我的意思：

#define INFINITY 9999999

struct floydEdge
{
    int weight;
    int steps;
};

floydEdge matrix[10][10];

int main()
{
    //We initialize the matrix
    for(int j=0;j<10;j++)
    {
        for(int k=0;k<10;k++)
        {
            matrix[j][k].weight=INFINITY;
            matrix[j][k].steps=0;
        }
    }

    //We input some weights
    for(int j=0;j<10;j++)
    {
        int a, b;
        cin>>a>>b;
        cin>>matrix[a][b].weight;
        matrix[b][a].weight=matrix[a][b].weight;
        matrix[a][b].steps=matrix[b][a].steps=1;
    }

    //We do the Floyd-Warshall, also checking for the step count as well as the weights
    for(int j=0;j<10;j++)
    {
        for(int k=0;k<10;k++)
        {
            for(int i=0;i<10;i++)
            {
                //We check if there is a shorter path between nodes j and k, using the node i. We also check if that path is shorter or equal to 4 steps.
                if((matrix[j][k].weight > matrix[j][i].weight + matrix[i][k].weight) && (matrix[j][i].steps+matrix[i][k].steps<=4))
                {
                    matrix[j][k].weight=matrix[k][j].weight=matrix[j][i].weight + matrix[i][k].weight;
                    matrix[j][k].steps=matrix[k][j].steps=matrix[j][i].steps+matrix[i][k].steps;
                }
                //If the path is not shorter, we can also check if the path is equal BUT requires less steps than the path we currently have.
                else if((matrix[j][k].weight == matrix[j][i].weight + matrix[i][k].weight) && (matrix[j][i].steps+matrix[i][k].steps<matrix[j][k].steps))
                {
                    matrix[j][k].weight=matrix[k][j].weight=matrix[j][i].weight + matrix[i][k].weight;
                    matrix[j][k].steps=matrix[k][j].steps=matrix[j][i].steps+matrix[i][k].steps;
                }
            }
        }
    }
    return 0;
}

我相信（但我不完全确定）这可以完美地工作（总是为所有节点之间提供最短路径）。试一试，让我知道！

于 2014-05-03T22:49:14.520 回答
0

是的，是的。

  • 算法的每次迭代都会添加一个单位长度的您搜索的路径。因此，如果您将迭代限制为 m，那么您会发现一条长度最多为 m 的路径。
  • 在 m -> n 的最坏情况下，复杂性将保持 O(n^3)。然而，更精确的估计是 O(m * n^2)。
于 2014-05-03T09:51:36.727 回答