Project: the shortest route

JavaScript · Unit 23: Data structures

A breadth-first walk reaches every point by the shortest path, because it moves level by level. What it doesn't tell you is what that path was.

To know it you write down, in another object, who brought each point. With that you can walk back from the destination to the origin.

const cameFrom = {
  lake: "downtown",
  fair: "lake",
};
let n = "fair";
while (n !== "downtown") {
  console.log(n);
  n = cameFrom[n];
}

Prints

fair
lake

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Predict the output
cameFrom says who brought each neighborhood. What does it print?
2. Complete the code
Fill in the blank to note who brought each neighborhood.
3. Put the lines in order
Put build(cameFrom, a, b) in order. It builds the route from a to b by following cameFrom backwards from the destination.
4. Write the code
Write route(g, a, b): it returns the list of neighborhoods from a to b, counting both, along the shortest path. If there's no way to get there, return an empty array. Every neighborhood is a key of g and its neighbors come in alphabetical order, so when two routes are the same length you keep the first one that arrives: that's the one that wins alphabetically at the first name where they differ. build is already written; you do the walk and fill in cameFrom.

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.