C++图算法的实现

发布于 12-11 07:15 字数 1333 浏览 0 评论 0原文

我正在尝试实现 广度优先搜索算法,以便找到两个顶点之间的最短距离。我开发了一个队列对象来保存和检索对象,并且我有一个二维数组来保存两个给定顶点之间的边的长度。我试图填充一个二维数组来保存两个顶点之间的最短距离。

然而,我遇到的问题是,无论我请求哪两个顶点的最短距离,都会返回 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];
               }
           }    
        }                 
     }  
}

I am trying to implement the Breadth-first search algorithm, in order to find the shortest distance between two vertices. I have developed a Queue object to hold and retrieve objects, and I have a two-dimensional array to hold the length of the edges between two given vertices. I am attempting to fill a two-dimensional array to hold the shortest distance between two vertices.

The problem I am having, however, is that no matter what two vertices I request the shortest distance of, 0 is returned. Here is my implementation of the algorithm; if you can set me on the right track and help me figure out my problem, that would be fantastic.

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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

戒ㄋ2024-12-18 07:15:10

好吧......我想问题是关于使用的算法和使用的术语。

“为了找到两个顶点之间的最短距离”你的意思是连通图中两个顶点之间的最短路径?

您尝试编写的算法是 Dijkstra 算法(这就是名称)。

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

Ok... i guess the problem is about the used algorithm and about used terms.

"In order to find the shortest distance between two vertices" you mean the shortest path between two vertices in a connected graph?

The algorithm you are trying to write is the Dijkstra's algorithm (this is the name).

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

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文