3

已编辑 - 12/03/12 @ 1:05 AM PST

我已按如下方式编辑了我的代码。但是，我仍然没有让它返回任何路径。

同样，此代码用于计算路径，由用户指定起始顶点和距离。该程序将返回与指定数据匹配的所有适当路径。

到目前为止，这是我的代码：

vector<vector<Vertex>> Graph::FindPaths(Graph &g, int startingIntersection, float distanceInMiles)
{   
/* A vector which contains vectors which will contain all of the suitable found paths. */
vector<vector<Vertex>> paths;

/* Create an empty set to store the visited nodes. */
unordered_set<int> visited;

/* Vector which will be used to the hold the current path. */
vector<Vertex> CurrentPathList;

/* Will be used to store the currerntVertex being examined. */
Vertex currentVertex;

/* Will be used to store the next vertex ID to be evaluated. */
int nextVertex;

/* Will be used to determine the location of the start ID of a vertex within the VertexList. */
int start;

/* Stack containing the current paths. */
stack<Vertex> currentPaths;

/* CurrentPathDistance will be used to determine the currernt distance of the path. */
float currentPathDistance = 0;

/* The startingIntersection location must be found within the VertexList.  This is because there is
 * no guarantee that the VertexList will hold sequential data.
 *
 * For example, the user inputs a startingIntersection of 73.  The Vertex for intersection #73 may 
 * be located at the 20th position of the VertexList (i.e. VertexList[20]). */
start = g.FindStartingIntersection(g, startingIntersection);

/* Push the startingIntersection onto the stack. */
currentPaths.push(g.VertexList[start]);

/* Continue to iterate through the stack until it is empty.  Once it is empty we have exhaused all
 * possible paths. */
while(!currentPaths.empty())
{
    /* Assign the top value of the stack to the currentVertex. */
    currentVertex = currentPaths.top();

    /* Pop the top element off of the stack. */
    currentPaths.pop();

    /* Check to see if we are back to the startingIntersection.  As a note, if we are just starting, it will 
     * put the startingIntersection into the paths. */
    if(currentVertex.id == startingIntersection)
    {
        /* Add currentVertex to a list. */
        CurrentPathList.push_back(currentVertex);

        /* Find the current path distance. */
        currentPathDistance = FindPathDistance(g, CurrentPathList);

        /* Check the currentPathDistance.  If it is within +/- 1 mile of the specified distance, then place
         * it into the vector of possible paths. */
        if((currentPathDistance + 1 >= distanceInMiles) && (currentPathDistance - 1 <= distanceInMiles))
        {
            paths.push_back(CurrentPathList);
        }
    }
    else /* The ending vertex was not the user specified starting vertex. */
    {
        /* Remove all elements from the stack. */
        while(!currentPaths.empty())
        {
            currentPaths.pop();
        }
    }

    nextVertex = FindUnvisitedNeighbor(g, currentVertex, visited);

    // repeat while current has unvisited neighbors
    while(nextVertex != -1)
    {
        /* Find the new starting vertex. */
        start = g.FindStartingIntersection(g, nextVertex);

        /* Push the startingIntersection onto the stack. */
        currentPaths.push(g.VertexList[start]);

        /* Push the next vertex into the visted list. */
        visited.insert(nextVertex);

        nextVertex = FindUnvisitedNeighbor(g, currentVertex, visited);
    }     
}

/* Return the vector of paths that meet the criteria specified by the user. */
return paths;

我的代码FindingUnvistedNeighbor()如下：

int FindUnvisitedNeighbor(Graph &g, Vertex v, unordered_set<int> visited)
{
    /* Traverse through vertex "v"'s EdgeList. */
    for(int i = 0; i + 1 <= v.EdgeList.size(); i++)
    {
        /* Create interator to traverse through the visited list to find a specified vertex. */
        unordered_set<int>::const_iterator got = visited.find(v.EdgeList[i].intersection_ID_second);

        /* The vertex was not found in the visited list. */
        if(got == visited.end())
        {

            return v.EdgeList[i].intersection_ID_second;
        }
    }

    return -1;
}
4

2 回答 2

0

深度优先就好。你必须中止

* path too long (bad)
* vertex already visited (bad)
* starting vertex visited (found a solution)

为了检测这些条件，您必须跟踪到目前为止访问的边/顶点

深度冷杉步行看起来像这样（完全未经检查）的伪代码
无论如何你应该明白

edge
    pair of node
    length

node
    list of edge

arrow               // incoming edge, node
    pair of edge, node

path
    list of arrow



check_node(arrow)   // incoming edge, node
    current_path.push(arrow)
    if length(current_path) > limit
        // abort too long
        current_path.pop(arrow)
        return
    if length(current_path) > 0 && current_path.first.node == current_path.last,node
        // found solution
        solutions.push(current_path)  // store the found solution and continue search
        current_path.pop(arrow)
        return
    if node in current_path
        // abort cycle
        current_path.pop(arrow)
        return
    for each edge in node
        // go deeper
        check(arrow(edge, edge.other_node))
    current_path.pop(arrow)
    return


main
    path current_path
    list of path solutions    // will hold all possible solutions after the check

    make_graph

    check_node(NULL, graph.start)

    for each solution in solutions   // print 0 .. n solutions
        print solution
于 2012-12-02T10:54:22.357 回答
0

这似乎是一个基本的算法问题，而不是一个特定于实现的问题，所以我为算法提供了详细的高级伪代码，而不是实际代码。另外，我不懂C++。如果有任何语法/逻辑不清楚，请告诉我，我可以澄清更多。它本质上是进行 DFS，但在找到值时不会停止：它会继续搜索，并报告该值的所有路径（符合给定距离标准）。

// Input: Graph G, Vertex start, Integer targetDistance
// Output: Set< List<Vertex> > paths
FindPaths ( G, start, targetDistance ):
    create an empty set, paths
    create an empty set, visited
    create an empty stack, currentPath

    // Iterative Exhaustive DFS
    push start on currentPath
    while ( currentPath is not empty ):
        current = pop ( currentPath )

        if ( current equals start ):
            copy currentPath to a list, L (reversed order doesn't matter)
            // find its weight
            w = FindPathWeight ( L, G )

            if ( w+1 >= targetDistance AND w-1 <= targetDistance ):
                add L to paths

        else if ( current is a dead-end ): drop it completely, it's useless

        x = FindUnvisitedNeighbor ( current, G, visited )
        // repeat while current has unvisited neighbors
        while ( x ):
            push x on currentPath
            add x to visited
            x = FindUnvisitedNeighbor ( current, G, visited )

    return paths
//EndFindPaths



// Input: List path, Graph G
// Output: Integer weight
FindPathWeight ( path, G ):
    Integer weight = 0;

    for each ( Vertex v in path ):

        if ( v is the end of the path ): break

        Consider the next vertex in the list, u
        Find the edge v——u in the graph, call it e
        Get the weight of e, w
        weight = weight + w

    return weight
//EndFindPathWeight



// Input: Vertex v, Graph G, Set visited
// Output: Vertex u (or null, if there are none)
FindUnvisitedNeighbor ( v, G, visited ):

    for each ( Edge v——u in G.EdgeList ):

        if ( u in visited ): continue

        // u is the first unvisited neighbor
        return u

    return null
//EndFindUnvisitedNeighbor
于 2012-12-02T13:02:26.187 回答