是否可以使用具有重量限制的 Floyd Warshall 算法（C++）计算最短路径？

Question

权重限制的要点是算法不应使用超过该限制的路径，即使它是最短路径。

因此，如果权重限制为 50，则在下图中，算法应选择从 0 到 2 的路径。 https://i.stack.imgur.com/I9SCL.png

这是使用 Floyd Warshall 算法找到最短路径的一些代码

for (unsigned int i = 0; i < m; i++)
{
    // Pick all vertices as source one by one
    for (unsigned int j = 0; j < m; j++)
    {
        // Pick all vertices as destination for the
        // above picked source
        for (unsigned int k = 0; k < m; k++)
        {
            // If vertex k is on the shortest path from
            // i to j, then update the value of dist[i][j]
            if (dist[i][k] + dist[k][j] < dist[i][j])
            {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

Answer 1

我很确定你 didn’t write that code。但无论如何，如果某些边因为“重量限制”而被禁止，那么在设置初始边成本时忽略它们即可。