如何找到顶点 i 和 j 之间的最小路径，它们之间最多有 S 顶点

Question

这是我实现弗洛伊德算法的代码。我如何更改此算法来解决此问题：求顶点 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

贝尔

曼-福特算法(略微修改的版本，不使用当前迭代中找到的路径(在每次迭代上i可以找到最多使用i边的所有最短路径。弗洛伊德-沃歇尔算法不是解决这类问题的合适方法。

你也可以修改Dijksta的算法，但它需要改变图形。修改后的图形将包含|V|*(S+1)顶点(对于每个顶点和每个可能的路径长度(。这个答案对图结构有详细的解释。