find_fastest_route.py

def find_fastest_route(self, from_vertex, to_vertex):
    """Finds for the shortest path from vertex a to b using
    Dijkstra's algorithm:
    https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
    Args:
        from_vertex (str) : Starting point on the graph
        to_vertex (str) : The final distanation
    Returns:
        shortest path (tuple): List of vertices in the path and len
                                Empty list if path does not exist
    """

    if from_vertex not in self.vert_dict or to_vertex not in self.vert_dict:
        raise KeyError("One of the vertex doesn't exist!")

    start_vertex = self.vert_dict[from_vertex]

    # if the goal and destination at the same vertex
    if from_vertex == to_vertex:
        return [start_vertex], 0

    # Initialize our priority queue and path
    queue = PriorityQueue()
    queue.put(PriorityEntry(0, start_vertex))
    path = {start_vertex.data: (0, None)}

    # Enqueue all vertices in the graph
    for vert_key, vert in self.vert_dict.items():
        if vert_key != start_vertex.data:
            path[vert_key] = (float("inf"), None)
            queue.put(PriorityEntry(float("inf"), vert))

    # While the queue isn't empty
    while not queue.empty():

        # Grab the piece of data from the queue and get it's current weight
        curr_vert = queue.get().data
        curr_vert_weight, _ = path[curr_vert.data]
        # Iterate through the neighbors of the current vertex
        for neighbor, weight in curr_vert.neighbors.items():

            # Get the neighbors weight
            prev_neighbor_weight, _ = path[neighbor.data]
            total_weight = weight + curr_vert_weight

            # Check if the new total weight is greater than what the
            # neighbors previous weight is
            if total_weight < prev_neighbor_weight:
                path[neighbor.data] = (total_weight, curr_vert)
                queue.put(PriorityEntry(total_weight, neighbor))

    # No path was found to the vertex, infinite weight away.
    total_weight, prev = path[to_vertex]
    if total_weight == float("inf"):
        return [], total_weight

    # Recreate the path
    goal = self.vert_dict[to_vertex]
    minimal_path = [goal]

    while prev:
        minimal_path.append(prev)
        _, prev = path[prev.data]

    # grab only vertex data to make it easy to visualize
    minimal_path = [node.data for node in minimal_path]

    return minimal_path[::-1], total_weight