1

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

4

2 回答 2

1

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

于 2012-12-05T09:01:59.323 回答
0

一种可能的方法。

你可以使用有界的best-first search.

创建一个结构，该结构P存储形成潜在循环的节点列表，以及到目前为止创建的循环的长度。

S通过为每个S链接到的节点创建一个单独的 P 结构，在指定的顶点进行搜索。将这些 P 结构添加到优先级队列中，该队列按 P 结构描述的路径长度排序。

考虑这些节点中的每一个依次从优先级队列中删除它们的 P 结构，复制它们的 P 结构，并附加它们链接到的节点。如果要添加的节点已经存在于 P 结构中而不是不存在S，则丢弃该结构并且不再考虑该路由。同样，如果任何路径超过指定的成本C，则丢弃该路径并且不再考虑它。如果路径没有被丢弃，则将其关联的 P 结构添加到优先级队列中。

如果S确实两次出现在一个P结构中，并且P结构描述的路径长度在允许的范围内，则成功退出。如果不是，则继续搜索，直到priortiy-queue 为空。

您可以通过使用可接受的启发式方法来加速算法来猜测从给定节点到 的距离S，将其添加到正在进行的路径的既定成本中，并使用总和作为优先级队列的排序键。这种启发式是A* 算法的核心，您可能会对此感兴趣。

这清楚吗？如果没有，我可以编写一个简短的示例代码。

于 2012-12-06T01:02:07.043 回答