Как рассчитать следующий? - PullRequest
Новая
       21

Как рассчитать следующий?

0 голосов
/ 08 апреля 2019

Итак, я реализую алгоритм Флойда-Варшалла.На каждом «Ex» какой-то код отсутствует, но я заполнил их все. Код все еще неверный, и я не знаю почему.

Если матрица смежности не бесконечна, то next[i,j] должно быть j? 

/// <summary>
/// EXERCISE 5: Floyd-Warshall Algorithm
/// </summary>
///
/// <param name="adjacencyMatrix">the adjacency matrix representing the graph</param>
/// <returns>a tuple containing 1. the distance matrix, 2. the next matrix</returns>
static Tuple<double[,], int[,]> FloydWarshall(double[,] adjacencyMatrix)
{
  var numVertices = adjacencyMatrix.GetLength(0);

  double[,] dist = new double[numVertices, numVertices];

  int[,] next = new int[numVertices, numVertices];

  for (int i = 0; i < numVertices; i++)
  {
    for (int j = 0; j < numVertices; j++)
    {
      if (i == j)
      {
        // TODO: Ex5.1; dist[i, j] = ?

        dist[i, j] = 0;
      }
      else
      {
        // TODO: EX5.2; dist[i, j] = ?

        dist[i, j] = adjacencyMatrix[i,j];
      }

      if (adjacencyMatrix[i, j] != Double.PositiveInfinity)
      {
        // TODO: Ex5.3; next[i, j] = ?

        next[i, j] = j;
      }
      else
      {
        next[i, j] = -1;
      }
    }
  }

  for (int k = 0; k < numVertices; k++)
  {
    for (int i = 0; i < numVertices; i++)
    {
      for (int j = 0; j < numVertices; j++)
      {
        //if (? < ?) { ... }
        // TODO: Ex5.4
        if (dist[i, k] + dist[k, j] < dist[i, j])
        {
          dist[i, j] = dist[i, k] + dist[k, j];
          next[i, j] = next[i, k];
        }
      }
    }
  }

  return new Tuple<double[,], int[,]>(dist, next);
}
...