C++图算法的实现
我正在尝试实现 广度优先搜索算法,以便找到两个顶点之间的最短距离。我开发了一个队列对象来保存和检索对象,并且我有一个二维数组来保存两个给定顶点之间的边的长度。我试图填充一个二维数组来保存两个顶点之间的最短距离。
然而,我遇到的问题是,无论我请求哪两个顶点的最短距离,都会返回 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];
}
}
}
}
}
好吧......我想问题是关于使用的算法和使用的术语。
“为了找到两个顶点之间的最短距离”你的意思是连通图中两个顶点之间的最短路径?
您尝试编写的算法是 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