Shortest Path in Unit Graph | Dataford Interview Questions

Synopsys VCS can analyze connectivity relationships among modules, ports, or signal endpoints. Given an undirected graph where every connection has unit distance, find the shortest path between two specified nodes.

Return the minimum number of edges needed to travel from source to target. If no path exists, return -1.

Formal Specification

Implement shortest_path(n, edges, source, target), where:

n is the number of vertices labeled 0 through n - 1.
edges is a list of two-element lists [u, v], representing an undirected edge between u and v.
source and target are valid vertex labels.
Return an integer representing the minimum edge count, or -1 when the target is unreachable.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
Each edge contains two distinct vertices in the range [0, n - 1]
No duplicate undirected edges appear
Every edge has unit distance

Function Signature

def shortest_path(n, edges, source, target):

Your question is Shortest Path in Unit Graph. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem