So finden Sie minimale Pfade zwischen den Scheitelpunkten i und j mit höchstens S Scheitelpunkten zwischen ihnen

Question

Hier ist mein Code zum Implementieren des Floyd-Algorithmus. Wie kann ich diesen Algorithmus ändern, um diese Frage zu lösen: Finde die minimalen Abstände zwischen den Scheitelpunkten i und j mit höchstens S Scheitelpunkten zwischen ihnen.

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 (die leicht modifizierte Version, die nicht gefunden Pfade von aktueller Iteration nicht verwendet) bei jeder Iteration i kann alle kürzesten Wege finden, die bei den meisten i Kanten verwenden. Der Floyd-Warshall-Algorithmus ist keine geeignete Methode, um diese Art von Problemen zu lösen.

Sie können auch Dijksta's algorithm ändern, aber es muss das Diagramm ändern. Modifizierter Graph enthält |V|*(S+1) Scheitelpunkte (für jeden Scheitelpunkt und jede mögliche Pfadlänge). Diese answer hat eine detaillierte Erläuterung der Graphenkonstruktion.