CODEWITHSUNDEEP
c++algorithm
Sergey
Sergey

Reputation: 441

Path reconstruction for Floyd-Warshall algorithm doesn't work for some values

I implement algorithm like there 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 constructor to initialize predecessors

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;
        }
    }
 }

this is matrix of lengths

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

It work only for some values,for example path from vertex 5 to vertex 0 builds(returns 5 2 0).But from 0 to 5 not builds(returns 5).Matrix of lengths builds correctly

Upvotes: 1

Views: 889

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

I think the problem is in this line (which looks for an impossible path):

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

Your nodes are indexed from zero, so a predecessor can legally be equal to 0. When a route involves node zero, you will incorrectly clear the path.

Try using this instead:

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

Upvotes: 2

Related Questions