I understand the basics of how a breadth-first search works. It utilizes a queue data structure to find adjacent vertices level by level.

My issue is in understanding how to find the shortest path between two vertices. In the example below, we assign newly visited vertices along with their edge to an array called edgeTo, but my question is how is the data stored? Is it a two-dimensional array? And how is it retrieved with the pathTo function?

The for loop in the pathTo function looks a bit odd to me, certainly because I might be new to it. How does this get the shortest path and how is the data structured or how is it saving the edges?

// add this to Graph class
this.edgeTo = [];
// bfs function
function bfs(s) {
    var queue = [];
    this.marked[s] = true;
    queue.push(s); // add to back of queue
    while (queue.length > 0) {
        var v = queue.shift(); // remove from front of queue
        if (v == undefined) {
            print("Visited vertex: "   v);
        }
        for each(var w in this.adj[v]) {
            if (!this.marked[w]) {
                this.edgeTo[w] = v;
                this.marked[w] = true;
                queue.push(w);
            }
        }
    }
}

function pathTo(v) {
    var source = 0;
    if (!this.hasPathTo(v)) {
        return undefined;
    }
    var path = [];
    for (var i = v; i != source; i = this.edgeTo[i]) { // this for loop is new to me 
        path.push(i);
    }
    path.push(s);
    return path;
}

function hasPathTo(v) {
    return this.marked[v];
}

CodePudding user response：

this.edgeTo is a simple array.

The BFS starts at the source vertex, and when it discovers a new vertex i, it sets edgeTo[i] to the predecessor vertex, which must necessarily be one step closer to the source.

In the pathTo function, the for loop follows the chain of edgeTo links from v back to the source. This enumerates the shortest path in reverse. These vertexes are appended to path as they are found.

pathTo then returns the path in reverse order, which is a little odd. A more usual implementation would reverse path before returning it, so that it would start at source and end at v. This function seems to be a little bugged in other ways, too. Maybe you're still working on it...