def shortest_paths(graph, vertex_key):
    """Uses Dijkstra's algorithm to find the shortest path from
    `vertex_key` to all other vertices.  If we have no lengths, then each
    edge has length 1.
    
    :return: `(lengths, prevs)` where `lengths` is a dictionary from key
        to length.  A length of -1 means that the vertex is not connected to
        `vertex_key`.  `prevs` is a dictionary from key to key, giving for
        each vertex the previous vertex in the path from `vertex_key` to that
        vertex.  Working backwards, you can hence construct all shortest
        paths.
    """
    shortest_length = { k : -1 for k in graph.vertices }
    shortest_length[vertex_key] = 0
    candidates = {vertex_key}
    done = set()
    prevs = {vertex_key:vertex_key}
    while len(candidates) > 0:
        next_vertex, min_dist = None, -1
        for v in candidates:
            dist = shortest_length[v]
            if min_dist == -1 or dist < min_dist:
                min_dist = dist
                next_vertex = v
        candidates.discard(next_vertex)
        done.add(next_vertex)

        for v in graph.neighbours(next_vertex):
            edge_index, _ = graph.find_edge(next_vertex, v)
            dist = min_dist + graph.length(edge_index)
            current_dist = shortest_length[v]
            if current_dist == -1 or current_dist > dist:
                shortest_length[v] = dist
                prevs[v] = next_vertex
            if v not in done:
                candidates.add(v)

    return shortest_length, prevs