Dijkstra's Algorithm

INTRODUCTION

One of the most popularly used algorithms in computer science is Dijkstra's algorithm. It is used in algorithms all over the place, from search to computer vision to routing. Its name comes from its creator, Edsger Dijkstra, who wrote a paper called "A note on two problems in connexion with graphs."

Dijkstra's technique finds the shortest path between any two nodes in a network. That may not sound like much, but it is pretty powerful - Dijkstra's is the algorithm that the internet uses to route your packets. It also has applications for finding the shortest paths through a maze or in terrain modeling.

Algorithm

function dijkstra(G, S)
    for each vertex V in G
        distance[V] <- infinite
        previous[V] <- NULL
        If V != S, add V to Priority Queue Q
    distance[S] <- 0

    while Q IS NOT EMPTY
        U <- Extract MIN from Q
        for each unvisited neighbour V of U
            tempDistance <- distance[U] + edge_weight(U, V)
            if tempDistance < distance[V]
                distance[V] <- tempDistance
                previous[V] <- U
    return distance[], previous[]

Explanation

It works like this: it removes one node from the graph at each step and adds it to an "undo queue." Whenever you remove a node from an undirected graph, you have to find a new path back to that node, which means you have to add all of its neighbours back on the graph.

The undo queue stores all of the nodes you've removed so far. Then it moves on to the next step. The next step removes another node and adds it to the undo queue; then it moves on again, releasing more nodes and adding them to the undo queue until it finally reaches a final state.

Example

To understand Dijkstra's algorithm and how it works, let us start with a scenario. Let's imagine that we have various towns scattered in different locations. We could travel along a road to go from one town to another. Not all roads have the same travel time though one road might take three minutes to travel through while another might take four. Furthermore, our question is, what is the fastest way to get from town A to town B? This is a specific example of a more general problem in graph theory where we have vertices, in this case, our towns, that are connected by edges.

In this case, our roads, together with the vertices and edges, form a graph. In particular, this graph is a weighted graph because each edge has some value or weight to indicate how costly it is to travel along that edge measured in either distance or time. We'd like to determine the shortest path from one vertex to another with this graph. So how does Dijkstra's algorithm allow us to do this? Ultimately we need to figure out how many minutes it will take to get to town B. It might be helpful to figure out how many minutes it would take to get to the other towns. So ideally, we'd want to label each town with a number representing the shortest time required to get there, but of course, we don't know that information yet, so instead, we will label each town with the shortest time we've found to get to that town before we have started the algorithm.

We don't have any known way of getting to the towns, so we'll label them all with infinity. The only town we can label correctly is our source town A which we can easily label. We're starting there, so it takes zero minutes to get to this town. Once we've found the shortest path to a town, let's call that town explored. For all other towns, we'll consider them unexplored. Dijkstra's algorithm repeats a two-step process. First, we update our estimates, and second, we choose the next vertex to explore.

Conclusion

This algorithm only works correctly if the weights of all of the edges are non-negative. Otherwise, some negative length path might result in the shortest path that our algorithm wouldn't be able to find. Another thing worth thinking about is how we efficiently determine which unexplored town to visit. Next, we want to always pick the unexplored town with the current smallest estimate. So some priority queue that gives us efficient access to the next town to visit can make our algorithm faster, and that's Dijkstra's algorithm for finding the shortest path in a graph. We keep track of the distance and a previous town for each vertex. The distance for all vertices starts at infinity except for the source at zero. Then as long as we haven't explored the destination yet, we pick the unexplored vertex with the smallest distance to explore. Next, we consider all edges connected to that vertex.