def predecessor_to_path(pred, source, target):
    """
    generate a path from source to target by pred
    @:param pred    a dict mapping each node to its predecessor node on the
                    shortest path from the specified starting node:
                    e.g. pred == {'b': 'a', 'c': 'b', 'd': 'c'}

    @:return    a list of the vertices in order along the shortest path.
                e.g. path = ['a', 'b', 'c', 'd']
    """
    v = target
    path = [v]
    while v != source:
        v = pred[v]
        path.append(v)
    path.reverse()
    return path