Algorithms: Solve 'Shortest Reach' Using BFS

Summary

Gayle Laakmann McDowell demonstrates how to implement the shortest reach algorithm using breadth-first search in code. She initializes key data structures like a queue and distances array, walks through traversing graph neighbors to update distances, and returns the final distances array. She emphasizes only using necessary variables, choosing the right algorithm upfront, and being comfortable with foundational graph search algorithms that come up in interviews and sometimes in real engineering work.

Takeaways

• 😊 Use BFS when trying to find the shortest path, as it is designed for that
• 👍 Have a queue to keep track of nodes to process next in BFS
• 🔑 No need for a separate visited array, can check if distance != -1
• 📏 Initialize distances array with -1, update to 0 for start node
• 😎 Distance to neighbor = distance to current node + 1
• ⚠️ Avoid too many unnecessary variables like visited array
• 🤔 Understand the problem before coding to know what's needed
• 🚫 DFS would not work well for shortest path problem
• 📚 Good to be familiar with BFS and DFS as fundamentals
• 💪 BFS useful for shortest path and real world problems

Q & A

What algorithm does Gayle recommend using for the shortest reach problem?

Gayle recommends using breadth-first search, as it is designed to find the shortest path between nodes in a graph.

Why does Gayle create a queue data structure?

Gayle creates a queue to track the next nodes to process in the breadth-first search. The queue follows the first-in, first-out ordering needed for BFS.

What array does Gayle initially create and then realize is unnecessary?

Gayle initially creates a boolean visited array to track which nodes have been visited. She then realizes it is unnecessary because that information is already encoded in the distances array.

How does the distances array work?

The distances array tracks the shortest distance from the start node to each other node. Unreached nodes are marked with -1, while reached nodes store the distance.

How is the distance to a neighbor node calculated?

The distance to a neighbor is the distance to the current node plus 1, representing the weight of the edge between them, which is defined to be 1.

What value does Gayle initialize the start node's distance to in the distances array?

Gayle initializes the start node's distance to 0 in the distances array, since the distance from a node to itself is 0.

What common mistake does Gayle say candidates make on this problem?

Gayle says a common mistake is using too many variables, like separate visited and distances arrays, instead of understanding what is actually necessary.

Why is depth-first search a poor choice for this problem?

Depth-first search is poor because it does not guarantee finding the shortest path between nodes like breadth-first search does.

Where can breadth-first and depth-first search be useful outside of interviews?

Breadth-first and depth-first search can be useful in real-world applications like social networking, routing algorithms, and AI pathfinding.

What key things does Gayle recommend remembering about graph searches?

Gayle recommends being comfortable with breadth-first and depth-first search, understanding when to apply each one, minimizing variables, and double checking your algorithm choice.