Pfadrekonstruktion für Floyd-Warshall-Algorithmus funktioniert nicht für einige Werte

Question

Ich implementiere Algorithmus wie dort http://en.algoritmy.net/article/45708/Floyd-Warshall-algorithm.

void Graph::floydWarshal() 
{ 
for (int k = 0; k < weight_matrix.size(); k++) 
{ 
    for (int i = 0; i < weight_matrix.size(); i++) 
    { 
     for (int j = 0; j < weight_matrix.size(); j++) 
     { 
      if (weight_matrix[i][k] != infinity && weight_matrix[k][j] != infinity) 
      { 
       int temp = weight_matrix[i][k] + weight_matrix[k][j]; 
       if (weight_matrix[i][j] > temp) 
       { 
        weight_matrix[i][j] = temp; 
        predecessors[i][j] = predecessors[k][j]; 
       } 
      } 
     } 
    } 
} 
} 

void Graph::getPath(int start, int finish, std::vector<int> &path) 
{ 
    if (start == finish) 
    { 
     path.push_back(start); 
    } 
    else if (predecessors[start][finish] == 0) 
    { 
     path.clear(); 
     return; 
    } 
    else 
    { 
     getPath(start, this->predecessors[start][finish], path); 
     path.push_back(finish); 
    } 
} 

in Konstruktor initialisiert Vorgängern

for (int i = 0; i < weight_matrix.size(); i++) 
    { 
    for (int j = 0; j < weight_matrix[i].size(); j++) 
    { 
     if (weight_matrix[i][j] != 0 && weight_matrix[i][j] != infinity) 
     { 
      predecessors[i][j] = i; 
     } 
     else 
     { 
      predecessors[i][j] = -1; 
     } 
    } 
} 

diese Matrix von Längen

0 2 1 4 inf inf 
2 0 7 3 inf inf 
1 i 0 5 10 4 
4 7 5 0 inf 5 
inf 3 10 inf 0 4 
inf inf 4 5 4 0 

Es funktioniert nur für einige Werte, beispielsweise Pfad vom Scheitel 5 bis Vertex 0 baut (Returns 5 2 0). Aber von 0 bis 5 nicht erstellt (returns 5) .Matrix der Längen baut sich korrekt auf

Answer 1

Ich denke, das Problem in dieser Linie ist (was für einen unmöglichen Weg sieht):

else if (predecessors[start][finish] == 0) 

Ihre Knoten von Null indiziert werden, so kann ein Vorgänger rechtlich gleich zu 0. Wenn eine Route Knoten beinhaltet Null, Sie wird den Pfad falsch löschen.

Versuchen Sie, diese anstelle:

else if (predecessors[start][finish] == -1)