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):