This lesson's interactive features are locked, please to keep using them

Dijkstra's Time Complexity

We opted for the "simple" implementation of Dijkstra's algorithm. We visit each node and check its distance to all of its neighbors. But there's a faster way that involves the use of a priority queue data structure. That more optimized implementation has a faster time complexity (Big-O) of O((N + E) * log(N)).

The priority queue approach is also explained by Lane in the video at lesson 3 in this chapter.

Graph = dict[str, dict[str, int]]


def dijkstra(graph: Graph, src: str, dest: str) -> list[str]:
    unvisited: set[str] = set()
    for node in graph:
        unvisited.add(node)

    distances: dict[str, float] = {}
    for node in graph:
        if node == src:
            distances[node] = 0
        else:
            distances[node] = float("inf")

    return dijkstra_r(graph, src, dest, unvisited, distances, {})


def dijkstra_r(
    graph: Graph,
    src: str,
    dest: str,
    unvisited: set[str],
    distances: dict[str, float],
    predecessors: dict[str, str],
) -> list[str]:
    if src == dest:
        path: list[str] = []
        pred: str | None = dest

        while pred is not None:
            path.append(pred)
            pred = predecessors.get(pred, None)

        path.reverse()
        return path

    for neighbor in graph[src]:
        if neighbor in unvisited:
            distance_so_far: float = distances[src]
            distance_to_neighbor: int = graph[src][neighbor]
            total_distance_to_neighbor: float = distance_so_far + distance_to_neighbor

            if total_distance_to_neighbor < distances[neighbor]:
                distances[neighbor] = total_distance_to_neighbor
                predecessors[neighbor] = src

    unvisited.remove(src)

    min_dist: float = float("inf")
    next_node: str | None = None
    for node in unvisited:
        if distances[node] < min_dist:
            min_dist = distances[node]
            next_node = node

    if next_node is None:
        return []

    return dijkstra_r(graph, next_node, dest, unvisited, distances, predecessors)