c++ - 从起点遍历图形并在起点处终止C++

我正在开发一个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的算法将仅存储从起始节点到任何其他节点的最短路径。相反，您想要的是跟踪通往节点的所有路径。如果有的话，则可以在每次找到节点的新路径时检查是否找到了一条路径，该路径的长度加上新路径的长度在用户指定距离的一个单位内。如果然后向前走一条路径，向后走另一条路径，那么您就会陷入困境。