如何找到頂點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有一個詳細的圖解結構的解釋。