Dijkstra's algorithm

The following is an excerpt from Dijkstra's original paper, entitled "A Note on Two Problems in Connexion with Graphs."

Construct tree of minimum total length between the n nodes. (The tree is a graph with one and only path between every two nodes.)

In the course of the construction that we present here, the branches are divided into three sets:

I. The branches definitely assigned to the tree under construction (they will be in a subtree);

II. The branches from which the next branch to be added to set I will be selected;

III. The remaining branches (rejected or not considered).

The nodes are divided into two sets:

A. The nodes connected by the branches of set I,

B. The remaining nodes (one and only one branch of set II will lead
to each of these nodes).

We start the construction by doing an arbitrary node as the only
member of set A, and by placing all branches that end in this node in set II. To start with set I is empty. From then onwards we perform the following two steps repeatedly.

Step 1: The shortest branch of set II is removed from this set and added to set I. As a result, one node is transferred from set B to set A.

Step 2: Consider the branches leading from the node, that has just
been transferred to set A, to the nodes that are still in set B. If the branch under construction is longer than the corresponding branch in set II, it is rejected; if it is shorter, it replaces the corresponding branch in set II, and the latter is rejected.

We then return to step I and repeat the process until sets II and B are empty. The branches in set I form the tree required.

E.W Dijkstra. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik, Vol. 1, 1959, pp. 269-271.

So, in a version adapted for routers, three databases represent the three sets of branches (i.e., I, II, and III).

• The Tree Database. Represents set I. Links (branches) are added to the SP tree here.
• The Candidate Database. For set II. Links from the LSDB (see following) are copied here in an order.
• The Link State Database. For set III. All links.

Set A and B would be routers, viz., the routers represented by Neighbor ID: Router, Neighbor, Cost). Set A comprises routers in the Tree DB, and Set B are all others. Se B, then, should be empty when the algorithm is finished.

Dijkstra's algorithm is the faster of two common algorithms to find all single-source shortest paths in a graph. That is, given a graph G and a root vertex r, Dijkstra will provide you with the shortest path from r to u where u is any vertex in G.

Notation

This writeup attempts to convey the essence of Dijkstra's algorithm with a minimum of formal math, nevertheless the following definitions are needed for clarity:

G = (V,E) - G is a graph which is defined by a set of vectors V and a set of edges E.
(u,v) - An arbitrary edge of G. Since shortest paths are most applicable to directed graphs, assume u is the source vertex and v is the target vertex.
w(u,v) - The weight of edge (u,v). This is technically a part of E.
d(u) - The total weight of the shortest path to u. When we start, the entire array is initialized to infinity (except the root). This is updated as we run through the algorithm.
p(u) - The predecessor of u on the shortest path. Since the shortest paths form a tree structure (ie. no cycles), every vertex needs only point to a predecessor to point the way back to the root. This is also updated as we go.
r - The root vertex. d(r) and p(r) can be initialized to special values indicating that it is the root, but it is a minor detail since the caller of the Dijkstra algorithm knows what root it requested.
Q - A priority queue used in the algorithm to keep track of the running lengths of unfound shortest paths.

Dijkstra's Insight

The Bellman-Ford algorithm is a more robust algorithm that solves the problem for all graphs with no negative-weight cycles. If a graph has a negative-weight cycle then obviously no shortest path exists because you can run through the cycle infinitely decreasing any path length. Essentially Bellman-Ford looks at every vertex |V| (number of vertices) times. At every loop, Bellman-Ford finds the shortest paths of the same length as the number of loops so far. After |V| loops we must have found all the shortest paths, because any longer path would have a cycle (by the pigeon hole principle), and in the absence of negative-weight cycles, the removal of such a cycle would produce a shorter path.

Dijkstra's is a greedy algorithm that adds an additional constraint in order to greatly decrease the number of edges considered at each step. Dijkstra's algorithm is only guaranteed to work on graphs that have no negative-weight edges at all. This constraint does little to diminish the usefulness of the algorithm since negative-weight edges are not normally found in real-world graphs (eg. networks).

Dijkstra's insight was quite simple, and very similar to Prim's algorithm. The idea is that if you split G into two sets of vertices A and B, the first being the set of vertices for which a shortest path is already known, and the second being all other vertices, you only need to consider edges crossing A and B to discover the shortest path to another vertex. If w(u,v) + d(u) is the shortest path, then you have found the shortest path to v. Why is this correct? Because any path to any other vertex will be longer, and because we have no negative weight edges, any longer paths to v will necessarily be longer still.

Bellman-Ford and Dijkstra's both run an outer loop |V| times, but Bellman-Ford considered every single edge, while Dijkstra limits itself to a select group of edges.

The only real tricky part of implementation is finding the next shortest path in each loop. Naively checking each vertex in B results in an algorithm that ends up being not much faster than Bellman-Ford. The trick is to keep a priority queue that contains all vertices in B and using d(u) as the key for every u in B.

Implementation of Dijkstra's Algorithm

The following is a pseudo-code rendition of Dijkstra's algorithm using mostly C-like syntax. Suggestions on improving clarity welcome.

Dijkstra(G,w,r) {
    initialize d(u) for all u to infinity
    initialize d(r) to 0
    initialize Q with all u using d(u) as keys
    while (Q is not empty) {
        u = Q.extractMin()
        for each vertex v that is adjacent to u (ie. u -> v) {
            if d(v) > d(u) + w(u,v) {
                d(v) = d(u) + w(u,v)
                p(v) = u
            }
        }
    }
    
    return p //A Predecessor vector is the most efficient representation of the final tree.
}

Imagine a graph - by which we mean dots and lines, vertices and edges, not x vs. y. Now imagine that each edge has a weight. This weight tells us how much it costs to go across that edge. It tells us what that edge's toll is. What is the cheapest way to get from point A to point B?

This problem stymied computer scientists for a while, and they came up with all these good ideas that never seemed quite right. Eventually, Dijkstra figured it all out, but there was still a problem: it was really hard to understand if you weren't already a computer scientist. So here is the best explanation of dijkstra's algorithm I have ever found. It is not 100% right, but it is much more right than it is wrong, and intuition is important here.

Imagine that instead of edges with costs, the edges are bits of string of different lengths. If the toll was $5.50, then the string is 5.5" long, and so on for all strings in the the graph. The strings' ends are then tied to little rings that are very very small, with one ring for each vertex. Now the problem is "how can I get from ring A to ring B while traversing the shortest amount of rope?" What Dijkstra saw to do was to pick up ring A, and slowly drag it off the ground until it dragged up its neighbors, which dragged up their neighbors, and so on until ring B was just barely off the ground. Now you should travel from A to B on all of the taut strings, and the amount of string used to do that is exactly the least amount of rope it takes to go from A to B, which is exactly the cheapest way to get from point A to point B. The total cost, if the rings are really small and B is just barely off the ground, will then be equal to the height of A!

So the next time you are faced with a problem like this, try to imagine making a model, and then see what happens! You might end up inventing something that gets taught to every single computer science undergraduate in the country and enables us to find directions on websites. With the right visualization techniques, the sky is the limit!