5.11. Dijkstra’s Algorithm

Edsger W. Dijkstra was a Dutch computer scientist who invented an efficient shortest-path algorithm. He also invented the semaphore, which is a data structure used to coordinate programs that communicate with each other. Dijkstra is famous (and notorious) as the author of a series of essays on computer science. Some, like “A Case against the GO TO Statement”, had a profound effect on programming practice. Others, like “On the Cruelty of Really Teaching Computing Science”, are entertaining in their cantankerousness, but less effective.

Dijkstra’s algorithm solves the “single source shortest path problem”, which means that it finds the minimum distance from a given “source” node to every other node in the graph (or at least every connected node).

We’ll present a simplified version of the algorithm that considers all edges the same length. The more general version works with any non-negative edge lengths.

The simplified version is similar to the breadth-first search in the previous section except that we replace the set called seen with a dictionary called dist, which maps from each node to its distance from the source:

def shortest_path_dijkstra(G, source):
dist = {source: 0}
queue = deque([source])
while queue:
    node = queue.popleft()
    new_dist = dist[node] + 1

    neighbors = set(G[node]).difference(dist)
    for n in neighbors:
        dist[n] = new_dist

return dist

Here’s how it works:

This algorithm only works if we use BFS, not DFS. To see why, consider this:

And so on. If you are familiar with proof by induction, you can see where this is going.

But this argument only works if we process all nodes with distance 1 before we start processing nodes with distance 2, and so on. And that’s exactly what BFS does.

In the exercises at the end of this chapter, you’ll write a version of Dijkstra’s algorithm using DFS, so you’ll have a chance to see what goes wrong.

Q-1: Summarize how the Dijkstra’s algorithm works.

You have attempted of activities on this page