algorithm - 如何找到顶点 i 和 j 之间最多有 S 个顶点的最小路径

Question

这是我实现 Floyd 算法的代码。我怎样才能改变这个算法来解决这个问题: 求顶点 i 和 j 之间至多 S 个顶点之间的最小距离。

void Floyd_Warshal(int graph[MAX][MAX], int D[MAX][MAX], int P[MAX][MAX], int numberOfNodes){
    for(int i = 0 ; i < numberOfNodes ; i++)
        for(int j = 0 ; j < numberOfNodes ; j++){
            D[i][j] = graph[i][j];
            P[i][j] = -1;
        }
    for(int k = 0 ; k < numberOfNodes ; k++)
        for(int i = 0 ; i < numberOfNodes ; i++)
            for(int j = 0 ; j < numberOfNodes ; j++)
                if(D[i][j] > D[i][k] + D[k][j]){
                    D[i][j] = D[i][k] + D[k][j];
                    P[i][j] = k;
                }
}

Answer 1

Bellman-Ford algorithm (略微修改的版本不使用当前迭代中找到的路径)在每次迭代中 i 可以找到最多使用 i 边的所有最短路径。 Floyd-Warshall 算法不是解决此类问题的合适方法。

可以修改Dijksta's algorithm同样，但它需要更改图形。修改后的图将包含 |V|*(S+1) 个顶点(对于每个顶点和每个可能的路径长度)。这answer对图的构造有详细的解释。