我正在开发一个C++程序，在该程序中，我们必须遍历顶点和加权边的图，方法是从用户指定的顶点开始，然后在经过某个所需距离后在同一顶点结束。我不确定如何用代码实现这一点，但到目前为止我已经有了：
void DijkstrasShortestPath()
{
while (vertices.size() != 0)
{
Vertex* u = extract_min(vertices);
vector<Vertex*>* adjVertex = AdjVertices(u);
const int size = adjVertex->size();
for (int i=0; i<size; ++i)
{
Vertex* v = adjVertex->at(i);
int distance = travel_dist(u, v) +
u->distFromStart;
if (distance < v->distFromStart)
{
v->distFromStart = distance;
v->previous = u;
}
}
delete adjVertex;
}
}
Vertex* extract_min(vector<Vertex*>& vertices)
{
int size = vertices.size();
if (size == 0) {
return NULL;
}
int minimum = 0;
Vertex* min = vertices.at(0);
int i = 0;
for( i=1; i<size; ++i)
{
Vertex* temp = vertices.at(i);
if( temp->distFromStart < min->distFromStart) {
min = temp;
minimum = i;
}
}
vertices.erase(vertices.begin() + minimum);
return min;
}
vector <Vertex*>* AdjVertices(Vertex* vert)
{
vector<Vertex*>* adjVertex = new vector <Vertex*> ();
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
Vertex* adjacent = NULL;
if (edge->intersection1 == vert)
{
adjacent = edge->intersection2;
}
else if (edge->intersection2 == vert)
{
adjacent = edge->intersection1;
}
if (adjacent && vertices_check(vertices, adjacent))
{
adjVertex->push_back(adjacent);
}
}
return adjVertex;
}
int travel_dist(Vertex* u, Vertex* v)
{
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
if (edge->street_connection(u, v))
{
return edge->distance;
}
}
return -1;
}
bool vertices_check(vector<Vertex*>& vertices, Vertex* vert)
{
const int size = vertices.size();
for(int i=0; i<size; ++i)
{
if (vert == vertices.at(i))
{
return true;
}
}
return false;
}
这本质上是Dijkstra的最短路径算法，这并不是我想要的。我想做的是让程序计算一条距离在用户指定距离的1个单位内，起点和终点在同一个顶点的路线。有什么办法可以通过改变我现有的东西来做到这一点吗？
这需要广度优先搜索还是深度优先搜索，而不是Dijkstra的算法？
Dijkstra的算法将只存储从起始节点到任何其他节点的最短路径。相反，您想要的是跟踪指向节点的所有路径。如果您有这些，您可以在每次找到节点的新路径时检查之前是否找到了长度加上新路径长度在用户指定距离的一个单位内的路径。如果你走一条路向前，另一条路向后，你就有了自己的环路。
一种可能的方法。
可以使用有界best-first search。
创建一个结构P，该结构存储形成潜在循环的节点列表，以及迄今为止创建的循环的长度。
通过为S链接到的每个节点创建一个单独的p结构，在指定的顶点S处为搜索设定种子。将这些p结构添加到优先级队列中，该队列按p结构描述的路径长度排序。
考虑依次从优先级队列中删除这些节点的p结构，复制它们的p结构并附加它们链接到的节点。如果要添加的节点已经存在于p结构中，而不是S，则丢弃该结构，不再考虑该路由。类似地，如果任何路径超过指定的成本C，则丢弃该路径，不再考虑它。如果路径尚未被丢弃，请将其关联的P结构添加到优先级队列中。
如果S确实出现在p结构中两次，并且p结构描述的路径长度在允许范围内，则成功退出。如果没有，请继续搜索，直到优先级队列为空。
您可以通过使用可接受的启发式方法来猜测从给定节点到S的距离，将其添加到正在进行的路径的既定成本中，并将总和用作优先级队列的排序关键字，从而加快算法的速度。这样的启发法是A*算法的核心，您可能对此感兴趣。
这清楚吗？如果没有，我可以写一个简短的示例代码。