Your question is Shortest Path in Directed Graph. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Blue Shield of California's member portal models certain service transitions as a directed graph. Given a graph, a starting service, and a destination service, return the sequence of vertices on a shortest directed path. Edge weights may be negative, but the graph contains no negative-weight cycle reachable from source.
Use the Bellman-Ford algorithm so negative edge weights are handled correctly. If the destination is unreachable, return an empty list. If source == target, return a list containing only that vertex.
Implement shortest_path(graph, source, target), where graph is a dictionary mapping each vertex to a list of [neighbor, weight] pairs. Vertices and source and target are strings, and weights are integers. Return a list of vertex strings from source to target, inclusive, representing a shortest path. Any shortest path is acceptable when multiple paths have equal total weight.
def shortest_path(graph, source, target):