Dijkstra's Shortest Path

From StoneHome

Dijkstra's Shortest Path is an algorithm operating on a graph of connected nodes, to find the lowest cost group of connections which will touch all nodes in the graph. The path which is created may (and often does) include branches. One notable aspect of this mechanism is that it can deal with paths whose weights are different in different directions. Another such aspect is that it's a relatively easy algorithm to implement. I don't really like the traditional terminology for discussing this algorithm, so I'll dispense with it.

Dijkstra's Shortest Path evaluates the entire graph. DSP is very efficient when the entire graph must be evaluated, but when only fractional evaluation will do - such as pathfinding within a larger map - one would be much better advised to use an algorithm which facilitates culling, such as A*.

The Setup

The Nodes

Let's start with a graph of nodes. We'll letter them A through F. Our goal is to find the path which will touch all of these nodes at the least cost. In order to determine cost, we establish connections between the nodes, each of which has an associated weight. In order to traverse the connection between two nodes, we must pay the established weight; therefore the cost of the total path is the cost of the sum of the weights from which it is made.

This algorithm is appropriate for a surprising variety of tasks; a simple example would be determining the best path for fiber optics through a workplace, where one sets the weights of a node relative to the number of bends the cable would need to make (because bends reduce the capacity of the fiber.) Another would be simulating the large-scale path of lightning with A* (where branching occurs due to low-pressure points in the atmosphere,) then solving shortest path between those subnodes with Dijkstra's Shortest Path or or Dijkstra's Walk.

Connections

Next, I begin making the conections between the nodes. These connections exist between every node pair. (Note, though, that I have omitted four pairs here: A⇒D, A⇒F, B⇒E and C⇒D.) Though they're not yet shown, each of these lines has a weight which measures how difficult or costly it is to traverse. It is on the basis of those costs which the cheapest path is determined.

Double Connections

We'll also include some double connections. These are connections whose weight is different in one direction than in the other. Granted that this example is a relatively unlikely layout, but this sort of behavior is nessecary in a bunch of different tasks (for example, routing traffic over a network with redundant asymmetric links.) Maybe more importantly, it's good to have a tool which can solve such a problem, because you will inevitably hit one eventually.

But B⇒E still isn't set.

Forbidden Connections

One has two options if one wants to make forbidden connections. One is to simply set the cost of the connection absurdly large. However, if legal routes are extremely long and forbidden routes extremely short between two points using that scheme theoretically things could fail (this takes a very extreme set of cases.) The other option is to simply keep a boolean with each weight indicating legal traversability; still, that's relatively expensive to keep checking, and at that point you're better advised to switch to Category:A*. Because the implementation is easier to understand with the very high weight approach, we'll use that for this brief tutorial.

Connection Weights

Well, so, admittedly even with my tacky Photoshop effects in place, the graph is a bit hard to read all at once. Luckily, in the time ahead we can look at no more than five at once, which will make this rather easier.

These are the weights which were discussed in section 1.2. They are integers, and to atraverse a path one pays the cost of all the subpaths summed. Therefore, for example, the path A⇒B⇒F costs 11+17 or 28 points. Note that the three double connections from section 1.3 have their node weights set differently in the directions indicated by the arrows. So, the path B⇒C⇒D⇒E costs 15+18+8 or 41, whereas the path E⇒D⇒C⇒B costs 8+21+15 or 44 - so different directions around the graph can generate different weights. (This example shows an example of this directional effect being resolved.)

How DSP Works

Let's do a step by step run of Dijkstra's Shortest Path. To begin with, we choose a point on the graph to begin evaluation from. Since the entire graph will be evaluated, it makes no difference where we begin; since it's most visually appealing, we'll begin at the top, at Node A.

Starting from Node A

Beginning from Node A, we have five outgoing connections: A→B (11), A→C (17), A→D (19), A→E (15), and A→F (14).