c++ - 从起点遍历图形并在起点结束 C++

Question

我正在开发一个 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 算法？

Answer 1

Dijkstra 算法只会存储从起始节点到任何其他节点的最短路径。相反，您想要的是跟踪通向节点的所有路径。如果你有这些，你可以在每次找到到节点的新路径时检查是否有一条路径之前已经找到，其长度加上新路径的长度在用户指定距离的一个单位内。如果你然后向前走一条路，另一条路向后走，你就有了你的循环。