COMP2521 W9 z5165557

// Given an array of visited vertices, where each element represents the parent of the vertex,
// fill the path array with the route between src and dest.
int reconstructShortestPath(Vertex src, Vertex dest, int *visited, int nV, int *path) {
        // Based on the suggestion here: https://stackoverflow.com/questions/8379785/how-does-a-breadth-first-search-work-when-looking-for-shortest-path#comment27820665_8379892

        // Record the route in a queue.
        Queue route = newQueue();

        // Backtrack through the visited array, recording each vertex in the queue.
        int current = dest;
        int length = 0;
        while(current != src) {
                QueueJoin(route, current);
                current = visited[current];
                length++;
        }

        // Add the source to the route.
        QueueJoin(route, src);
        length++;

        // Convert the queue into an array of vertices in order from src to dest.
        int i;
        for (i = length - 1; i >= 0; i--) {
                path[i] = QueueLeave(route);
        }

        return length;
}

// find a path between two vertices using breadth-first traversal
// only allow edges whose weight is less than "max"
int findPath(Graph g, Vertex src, Vertex dest, int max, int *path)
{
        // Based on the BFS pseudocode from https://en.wikipedia.org/wiki/Breadth-first_search

        assert(g != NULL);

        // Special case: if travelling to the starting destination, just return it.
        if (src == dest) {
                path[0] = src;
                return 1;
        }


        // Create a queue of nodes to visit; when this is empty the search is complete.
        Queue toVisit = newQueue();
        QueueJoin(toVisit, src);

        // Create an array, where each index represents the "parent" of the vertex. If the vertex has not
        // yet been visited, it will be -1.
        int *visited = malloc(sizeof(int)*g->nV);
        int v;
        for(v = 0; v < g->nV; v++) {
                visited[v] = -1;
        }

        // Perform the BFS.
        while (!QueueIsEmpty(toVisit)) {
                // Take next vertex to visit from the queue.
                Vertex currentVertex = QueueLeave(toVisit);

                // If this vertex is the destination, we're done, so return the path.
                if (currentVertex == dest) {
                        return reconstructShortestPath(src, dest, visited, g->nV, path);
                }

                // Loop through the children of the current vertex.
                int child;
                for (child = 0; child < g->nV; child++) {
                        // If there is no edge to the vertex, skip it (filter out non-children).
                        if (g->edges[currentVertex][child] == 0) continue;

                        // If the distance to the vertex is greater than the plane can fly, skip it.
                        if (g->edges[currentVertex][child] > max) continue;

                        // If the vertex has already been visited, skip it.
                        if (visited[child] != -1) continue;

                        // Add the child to the queue to be visited.
                        QueueJoin(toVisit, child);

                        // Record the parent of the child.
                        visited[child] = currentVertex;
                }
        }

        // If there is no path, return a length of 0.
        return 0;
}