Shortest Path Approach

In this lesson, Alvin explores the strategy to solving the following interview problem:

Write a function, shortest_path, that takes in a list of edges for an undirected graph and two nodes (*node_A*, node_B). The function should return the length of the shortest path between A and B. Consider the length as the number of edges in the path, not the number of nodes. If there is no path between A and B, then return -1. You can assume that A and B exist as nodes in the graph.

edges = [
['w', 'x'],
['x', 'y'],
['z', 'y'],
['z', 'v'],
['w', 'v']
]

shortest_path(edges, 'w', 'z') # -> 2

edges = [
['w', 'x'],
['x', 'y'],
['z', 'y'],
['z', 'v'],
['w', 'v']
]

shortest_path(edges, 'y', 'x') # -> 1

edges = [
['a', 'c'],
['a', 'b'],
['c', 'b'],
['c', 'd'],
['b', 'd'],
['e', 'd'],
['g', 'f']
]

shortest_path(edges, 'a', 'e') # -> 3

If you need additional support taking these DSA skills and actually applying them, take Alvin's complete data structures and algorithms course on Structy. You can try out the concepts yourself in their interactive code editor and learn advanced DSA patterns like stack exhaustive recursion.

Use this link to get 20% off the entire Structy DSA learning experience.

Follow Alvin on LinkedIn: https://www.linkedin.com/in/alvin-zablan-b73a92117/