頂点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には、グラフの構成の詳細な説明があります。