如何找到顶点i和j之间至多有顶点之间的最小路径

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有一个详细的图解结构的解释。