c++shortest-pathfloyd-warshall

Is it possible to calculate the shortest path using Floyd Warshall's algorithm with a weight limit (C++)?


The point of the weight limit is that the algorithm should not use paths that exceed that limit even if it is the shortest path.

So if the weight limit was 50, in the graph below the algorithm should choose the path from 0 to 2. https://i.sstatic.net/I9SCL.png

This is some code to find the shortest path using Floyd Warshall's algorithm

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];
            }
        }
    }
}

Solution

  • I’m pretty sure you didn’t write that code. But in any case, if certain edges should be disallowed because of a “ weight limit”, just ignore them when setting the initial edge costs.