ECON 895 · Week 7

Dijkstra's Algorithm Step by Step

Noel D. Johnson · Spatial Techniques for Empirical Economics · George Mason University

1A six-node network

Each line is a road with a cost of travel. Dijkstra's algorithm finds the cheapest cost from one starting node to every other node. It keeps a tentative cost for every node and a set of settled nodes. At each step it settles the unsettled node with the lowest tentative cost and then relaxes that node's roads. Relaxing a road means lowering a neighbor's tentative cost when the route through the settled node is cheaper.

Start at
not reached reached, cost tentative settled this step settled
Figure 1. The network from the Week 7 slides. The number under each node is its tentative cost. Rust roads are the ones relaxed in the current step. Teal roads form the cheapest route to each settled node. After the last step click any node to trace its cheapest route from the start. Change a road's cost in the boxes below the table and the run starts over.

A settled node's cost never changes again. When it is settled every other unsettled node already costs at least as much, and with costs that are never negative no later route can come back cheaper. That is why the algorithm needs nonnegative costs.

2A raster is a graph

Every cell of a raster is a node and every cell touches its eight neighbors. The cost of a step between two cells is the mean of their costs times the distance between their centers, so a diagonal step costs 1.41 times a straight one. This is what gdistance builds with transition and geoCorrection, and the algorithm is the same as above. Paint cells with a mode of transport, then find the cheapest route.

Paint Place
–cost of the cheapest route, km-equivalents
–length of that route, km
–straight-line distance, km
–cells settled before the end was reached
Figure 2. Each cell is 10 km across. The costs are Bairoch's relative costs used in the Week 7 code, overland 1, road 0.81, river 0.21, and sea 0.08. Shading shows the order in which cells were settled, lightest first. The route is drawn in rust. Click or drag to paint.