Solve shortest and label-similar paths
Overview
This question evaluates proficiency in graph algorithms and sequence-matching techniques, testing graph traversal and pathfinding competencies as well as dynamic-programming-style approaches for minimizing label mismatches.
Part A — Unweighted shortest path: You are given an undirected, unweighted graph with vertices labeled 0..n-1 and an edge list. Given start node s and target node t, return both the length and one actual shortest path (as a list of vertices). If no path exists, return an empty list. Discuss your algorithm and its time and space complexity. Part B — Path matching a label sequence with minimal mismatches: Each vertex i has a string label name[i]. Given a sequence target[0..m-1] of labels, find a path v0..v_{m-1} such that consecutive vertices are adjacent in the graph and the number of indices i where name[v_i] != target[i] is minimized. Return one optimal vertex sequence. Explain your approach, how you reconstruct the path, and analyze complexity for n up to 10^4, edges up to 10^4, and m up to 10^3.