How does this findRoute function work in Chapter 7 of Eloquent Javascript 3rd Edition?

JavaScript
1

In the Chapter 7 of Eloquent Javascript 3rd Edition, the author creates a function findRoute to find the shortest route between two locations. It’s so hard to understand it for beginners like me. Can anybody help explain how it works?

The roadGraph is the map data that will be passed to the findRoute function as graph:

    // Places and roads of Meadowfield

    const roads = [
      "Alice's House-Bob's House", "Alice's House-Cabin",
      "Alice's House-Post Office", "Bob's House-Town Hall",
      "Daria's House-Ernie's House", "Daria's House-Town Hall",
      "Ernie's House-Grete's House", "Grete's House-Farm",
      "Grete's House-Shop", "Marketplace-Farm",
      "Marketplace-Post Office", "Marketplace-Shop",
      "Marketplace-Town Hall", "Shop-Town Hall"
    ];


    //function to convert the roads into a data structure

    function buildGraph(edges) {

      let graph = Object.create(null);

      function addEdge(from, to) {

        if (graph[from] == null) {
          graph[from] = [to];
        } else {
          graph[from].push(to);
        }
      }

      for (let [from, to] of edges.map(r => r.split("-"))) {
        addEdge(from, to);
        addEdge(to, from);
      }

      return graph;

    }

    // assign the data structure to roadGraph

    const roadGraph = buildGraph(roads);


    // The function that searches the shortest route between two places in roadGraph

    function findRoute(graph, from, to) {


      let work = [{
        at: from,
        route: []
      }];


      for (let i = 0; i < work.length; i++) {

        let {
          at,
          route
        } = work[i];

        // I'm especially confused on the following loop
        
        for (let place of graph[at]) {

          if (place == to) return route.concat(place);

          // so confuesd on the following if statement, how does it work at all?
          
          if (!work.some(w => w.at == place)) {
            work.push({
              at: place,
              route: route.concat(place)
            });
          }

        }

      }

    }
1 Like
2

Might be helpful

1 Like
4

This is the easy version of the findRoute() function.

function findRoute(graph, from, to){

    let result = [{at : from, route : []}];
    for(let i = 0; i < result.length; i++){
        let {at, route} = result[i];
        for(place of graph[at]){
            if(place != to){
                result.push({at : place, route : route.concat(place)});
            }else{
                return route.concat(place);
            }
        }
    }
}