Dijkstra's Algorithm

Let's now turn to a new problem that graphs can help us solve: the shortest path problem. It's often useful to know the shortest path from one vertex to another – i.e., the one with the minimal total cost. This can help in applications such as routing traffic in the Internet.

For an unweighted graph, we can simply do the following:

1. Start a breadth-first traversal from the origin, $$v$$
2. Stop the traversal when you reach the other vertex, $$w$$
3. The path from $$v$$ to $$w$$ in the resulting (possibly partial) spanning tree is a shortest path

A breadth-first traversal works for an unweighted graph because the shortest path is simply the one with the fewest edges, and a breadth-first traversal visits cities in order according to the number of edges they are from the origin.

For weighted graphs, there are multiple algorithms that find the shortest paths. One very famous example is Dijkstra's algorithm.

Dijkstra's algorithm

Dijkstra's algorithm allows us to find the shortest path from a vertex $$v$$ (the origin) to all other vertices that can be reached from $$v$$.

The basic idea is to maintain estimates of the shortest paths from the origin to every vertex (along with their costs), and gradually refine these estimates as we traverse the graph

Watch the video below to see how Dijkstra's algorithm works:

Implementation

We can now add Dijkstra's algorithm to our graph.py file:

    def dijkstra(self, origin_id):
        self.reinit_vertices()
        origin = self.get_vertex(origin_id)
        if origin is None:
            raise ValueError(f"No such vertex: {origin_id}")
        origin.cost = 0

        while True:
            w = None
            v = self.vertices
            while v:
                if not v.done and (w is None or v.cost < w.cost):
                    w = v
                v = v.next

            if w is None or w.cost == float('inf'):
                return

            print(f"\tfinalizing {w.id} (cost = {w.cost}" +
                  (f", parent = {w.parent.id})" if w.parent else ")"))
            print(f"\t\tpath = {w.path_string()}")
            w.done = True

            edge = w.edges
            while edge:
                x = edge.end
                if not x.done:
                    cost_via_w = w.cost + edge.cost
                    if cost_via_w < x.cost:
                        x.cost = cost_via_w
                        x.parent = w
                edge = edge.next

Try adding this code to your graph.py file and running it with an example graph.

Example

Recall the graph that we've been using that represents some cities and roads in a map (note: some of the edge weights have been slightly changed from previous versions so that the output of the algorithm is more interesting):

Time analysis

The time complexity of Dijkstra's algorithm depends in part on what technique is used to select the vertex with the next-smallest estimate in order to finalize it. For example, for every iteration of the algorithm, we could scan over the entire list of vertices, but a faster way would be to store the vertices in a min-at-top priority queue, where the priority is the vertex's current shortest path estimate. This way, we could repeatedly remove the next-smallest estimate vertex and finalize it.

When using a priority queue, each operation to the extract the minimum takes $$O(log|V|)$$ time, and there are $$|V|$$ such operations. Over the course of the algorithm, vertexes are decreased according to the $$|E|$$ edges, and each decrease operation requires $$O(log|V|)$$ time, since you must search through the heap for the vertex whose estimate you want to decrease. Therefore, the running time is $$O(|E|*log|V| + |V|*log|V|) = O((|E| + |V|)log|V|)$$. In most cases, $$|E| > |V|$$, so often the running time is written as $$O(|E|log|V|)$$.

Summary

Watch the following video to see a quick summary of Dijkstra's algorithm: