Реализация алгоритма графов на C ++ - PullRequest
Новая
       25

Реализация алгоритма графов на C ++

1 голос
/ 23 октября 2011

Я пытаюсь реализовать алгоритм поиска в ширину , чтобы найти кратчайшее расстояние между двумя вершинами.Я разработал объект Queue для хранения и извлечения объектов, и у меня есть двумерный массив для хранения длины ребер между двумя заданными вершинами.Я пытаюсь заполнить двумерный массив, чтобы удерживать самое короткое расстояние между двумя вершинами.

Однако проблема, с которой я сталкиваюсь, заключается в том, что независимо от того, какие две вершины я запрашиваю самые короткиерасстояние, 0 возвращается.Вот моя реализация алгоритма;если бы вы смогли направить меня в нужное русло и помочь разобраться в моей проблеме, это было бы замечательно. 

 for (int i = 0; i < number_of_vertex; i++) 
 //For every vertex, so that we may fill   the array
 {
  int[] dist = new int[number_of_vertex]; 
  //Initialize a new array to hold the values for the distances

for (int j = 0; x < number_of_vertex; j++)
{
    dist[j] = -1; 
   //All distance values will be set to -1 by default; this will be changed later on
 }

  dist[i] = 0; //The source node's distance is set to 0 (Pseudocode line 4)

   myQueue.add(i); //Add the source node's number to the queue (Pseudocode line 3)

   while (!myQueue.empty()) //Pseudocode line 5
   {
      int u = myQueue.eject(); //Pseudocode line 6

      for (int y = 0; y < number_of_vertex; y++) //Pseudocode line 7
      {
          if (edge_distance(u,y) > 0)
          {
              if (dist[y] == -1)
              {
                  myQueue.add(y);
                  dist[y] = dist[u] + 1;
                  shortest_distance[i][u] = dist[y];
               }
           }    
        }                 
     }  
}

1 Ответ

1 голос
/ 23 октября 2011

Хорошо ... я думаю, проблема в используемом алгоритме и в используемых терминах.

"Чтобы найти кратчайшее расстояние между двумя вершинами", вы имеете в виду кратчайший путь между двумя вершинами в соединеннойgraph?

Алгоритм, который вы пытаетесь написать, является алгоритмом Дейкстры (это название).

http://www.cs.berkeley.edu/~vazirani/algorithms/chap4.pdf

...