Appendix 7: worked calculation example

What’s the problem?

It’s 11:30am on September 6th 2001, I’m in Richmond Road (postcode B1 1TP) in the Bristol area and I want to get to Wolfson College, Oxford (OX2 6UD) in time to change and hand in my thesis. How does Dijkstra's algorithm work it out?

Step 1: generate a route table

Please note that:-

The information is duplicated: for example, the road from Banbury to Bristol is held separately from the road from Bristol to Banbury, even though they're the same road.
The information is split into "machine values" (short, logical phrases like "A", "car" or "99999999") and "human values" (vaguer, fuzzy phrases like "70 km" or "B476"). The "machine values" will be used by the calculation program but the "human values" will be used by the translation programs.
This information can be derived from a database or (if speed is a factor, and it invariably is), a hardcoded file.

Route name (M)	Route name (H)	Route duration in minutes (M)	Start node (M)	Start node (H)	Finish node (M)	Finish node (H)	Route length (H)	Birthday in minutes since 2000 (M)	Deathday in minutes since 2000 (M)	Route orie (M)	Route mode (M)
A	A232	00000090	1	Banbury	2	Bristol	70km	00000000	99999999	SW	car
B	B476	00000040	1	Banbury	4	Oxford	40km	00000000	99999999	SE	car
C	A232	00000090	2	Bristol	1	Banbury	70km	00000000	99999999	NE	car
D	M4	00000020	2	Bristol	6	Swindon	40km	00000000	99999999	SE	car
E	B476	00000040	4	Oxford	1	Banbury	40km	00000000	99999999	NW	car
F	M2	00000005	4	Oxford	5	Reading	10km	00000000	99999999	S	car
G	A999	00000100	4	Oxford	6	Swindon	30km	00000000	99999999	SW	car
H	M2	00000005	5	Reading	4	Oxford	10km	00000000	99999999	N	car
I	M4	00000090	5	Reading	6	Swindon	90km	00000000	99999999	W	car
J	M4	00000020	6	Swindon	2	Bristol	40km	00000000	99999999	NW	car
K	A999	00000100	6	Swindon	4	Oxford	30km	00000000	99999999	NE	car
L	M4	00000090	6	Swindon	5	Reading	90km	00000000	99999999	E	car

Step 2: generate a node table

This contains the name of each node and a pointer to the first of the routes out of there
Again, this can be generated from a database or a hardcoded file.

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
						1	Banbury		A, B	N
						2	Bristol		C, D	N
						4	Oxford		E, F, G	N
						5	Reading		H, I	N
						6	Swindon		J, K, L	N

Step 3: generate a postcode-to-nearest-node table

Obviously, the production one is bigger…

Postcode	Nearest node
B1	Bristol
OX2	Oxford

Step 4: get the nearest nodes and update the node table

We get the origin node (the nearest node to B1 1TP, ie Bristol) and the destination node (the nearest node to OX2 6UD, ie Oxford) We assume that it’ll take 30 minutes to get to the origin node, so we’ll be starting from there at noon on Sept 6th 2001. In our time standard, that’s 884880 minutes since Jan 1st 2000, so we update the node table thus:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
						1	Banbury		A, B	N
-	-	-	-	-	-	2	Bristol	884880	C, D	N
						4	Oxford		E, F, G	N
						5	Reading		H, I	N
						6	Swindon		J, K, L	N

Step 5: Look through the list of unknowns and mark the shortest as known.

Well, we’ve only got one non-null unknown duration (Bristol), so mark that as known, thus:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
						1	Banbury		A, B	N
-	-	-	-	-	-	2	Bristol	884880	C, D	Y
						4	Oxford		E, F, G	N
						5	Reading		H, I	N
						6	Swindon		J, K, L	N

Step 6: Take your new known node and visit its neighbours

It takes 90 minutes to get from Bristol to Banbury via the A232, so we can get there by 1.30pm. Similarly, it takes 20 minutes to get from Bristol to Swindon via the M4, so we can get there by twenty past twelve. Update the figures thus:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
2	Bristol	NE	A232	70km	car	1	Banbury	884970	A, B	N
-	-	-	-	-	-	2	Bristol	884880	C, D	Y
						4	Oxford		E, F, G	N
						5	Reading		H, I	N
2	Bristol	SE	M4	40km	car	6	Swindon	884900	J, K, L	N

Step 7: Look through the list of unknowns and mark the shortest as known

OK, we’ve got 3 non-null durations, and one of them (Bristol) is already known. That leaves Banbury and Swindon, and Swindon’s the shortest. So mark Swindon as known, thus:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
2	Bristol	NE	A232	70km	car	1	Banbury	884970	A, B	N
-	-	-	-	-	-	2	Bristol	884880	C, D	Y
						4	Oxford		E, F, G	N
						5	Reading		H, I	N
2	Bristol	SE	M4	40km	car	6	Swindon	884900	J, K, L	Y

Step 8: Take your new known node and visit its neighbours

OK, we know we can be in Swindon by twenty past twelve. Now what? Well, it takes 100 minutes to get from Swindon to Oxford via the A999, so we can get there by 2pm. Similarly, it takes 90 minutes to get from Reading to Swindon via the M4, so we can get there by ten to two. We update the figures thus:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
2	Bristol	NE	A232	70km	car	1	Banbury	884970	A, B	N
-	-	-	-	-	-	2	Bristol	884880	C, D	Y
6	Swindon	NE	A999	30km	car	4	Oxford	885000	E, F, G	N
6	Swindon	E	M4	90km	car	5	Reading	884990	H, I	N
2	Bristol	SE	M4	40km	car	6	Swindon	884900	J, K, L	Y

and loop round again…

Step 9: Look through the list of unknowns and mark the shortest as known

OK, we’ve got 5 non-null durations, but two of them are known. That leaves Banbury, Reading and Oxford, and Banbury’s the shortest. So mark Banbury as known, thus:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
2	Bristol	NE	A232	70km	car	1	Banbury	884970	A, B	Y
-	-	-	-	-	-	2	Bristol	884880	C, D	Y
6	Swindon	NE	A999	30km	car	4	Oxford	885000	E, F, G	N
6	Swindon	E	M4	90km	car	5	Reading	884990	H, I	N
2	Bristol	SE	M4	40km	car	6	Swindon	884900	J, K, L	Y

Step 10: Take your new known node and visit its neighbours

OK, we know we can be in Banbury by one-thirty. Where next? Well, it takes 40 minutes to get from Banbury to Oxford via the B476, so we can get there by ten past two. Problem is, we already have a route to Oxford that’ll get us there by 2pm, so ignore that. The figures stay like this:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
2	Bristol	NE	A232	70km	car	1	Banbury	884970	A, B	Y
-	-	P>-	-	-	-	2	Bristol	884880	C, D	Y
6	Swindon	NE	A999	30km	car	4	Oxford	885000	E, F, G	N
6	Swindon	E	M4	90km	car	5	Reading	884990	H, I	N
2	Bristol	SE	M4	40km	car	6	Swindon	884900	J, K, L	Y

and loop round again…

Step 11: Look through the list of unknowns and mark the shortest as known

OK, we’ve got 5 non-null durations, but three of them are known. That leaves Reading and Oxford, and Reading’s the shortest. So mark Reading as known, thus:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
2	Bristol	NE	A232	70km	car	1	Banbury	884970	A, B	Y
-	-	-	-	-	-	2	Bristol	884880	C, D	Y
6	Swindon	NE	A999	30km	car	4	Oxford	885000	E, F, G	N
6	Swindon	E	M4	90km	car	5	Reading	884990	H, I	Y
2	Bristol	SE	M4	40km	car	6	Swindon	884900	J, K, L	Y

Step 12: Take your new known node and visit its neighbours

OK, we know we can be in Reading by ten-to-two. Where next? Well, it takes 5 minutes to get from Oxford from Reading via the very fast (and sadly mythical) M2, so we can get there by five to two. That’s quicker than our existing route, so update the figures thus:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
2	Bristol	NE	A232	70km	car	1	Banbury	884970	A, B	Y
-	-	-	-	-	-	2	Bristol	884880	C, D	Y
5	Reading	N	M2	10km	car	4	Oxford	884995	E, F, G	N
6	Swindon	E	M4	90km	car	5	Reading	884990	H, I	Y
2	Bristol	SE	M4	40km	car	6	Swindon	884900	J, K, L	Y

and loop round again…

Step 13: Look through the list of unknowns and mark the shortest as known

OK, there’s only one non-null duration, so mark that as known. Even better, it’s Oxford, so our quest is over…

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
2	Bristol	NE	A232	70km	car	1	Banbury	884970	A, B	Y
-	-	-	-	-	-	2	Bristol	884880	C, D	Y
5	Reading	N	M2	10km	car	4	Oxford	884995	E, F, G	Y
6	Swindon	E	M4	90km	car	5	Reading	884990	H, I	Y
2	Bristol	SE	M4	40km	car	6	Swindon	884900	J, K, L	Y

Step 14: Tag the information.

We go through the table and tag it thus:-

Back node (M)	Back node (H)	Back route orie (M)	Back route name (H)	Back route len (H)	Back route mode (H)	Node (M)	Node (H)	Duration (M)	Routes out (M)	Known (M)
<A2A>	<HBristolH>	<ENEE>	<CA232C>	<D70kmD>	<FcarF>	<B1B>	<IBanburyI>	<G884970G>	A, B	Y
-	-	-	-	-	-	<B2B>	<IBristol I>	<G884880G>	C, D	Y
<A5A>	<HReadingH>	<ENE>	<CM2C>	<D10kmD>	<FcarF>	<B4B>	<IOxford I>	<G884995G>	E, F, G	Y
<A6A>	<HSwindonH>	<EEE>	<CM4C>	<D90kmD>	<FcarF>	<B5B>	<IReadingI>	<G884990G>	H, I	Y
<A2A>	<HBristolH>	<ESEE>	<CM4C>	<D40kmD>	<FcarF>	<B6B>	<ISwindonI>	<G884900G>	J, K, L	Y

Step 15: Print out the required information

Go through the table following the backlinks backwards and print out the tagged information

<A5A><HReadingH><ENE><CM2C><D10kmD><FcarF><B4B><IOxford I><G 884995 G>
<A6A><HSwindonH><EEE><CM4C><D90kmD><FcarF><B5B><IReading I><G 884990 G>
<A2A><HBristolH><ESEE><CM4C><D40kmD><FcarF><B6B><ISwindon I><G 884900 G>

Step 16: Reverse it

The route is deduced backwards so reverse it.

<A2A><HBristolH><ESEE><CM4C><D40kmD><FcarF><B6B><ISwindon I><G 884900 G>
<A6A><HSwindonH><EEE><CM4C><D90kmD><FcarF><B5B><IReading I><G 884990 G>
<A5A><HReadingH><ENE><CM2C><D10kmD><FcarF><B4B><IOxford I><G 884995 G>

Step 17: Add the first and last lines.

This route is from the origin node to the destination node. Don’t forget to add a line from the origin postcode to the origin node, and another line from the destination node to the destination postcode. Note that you won’t be able to complete all the tags for those parts of the route.

<HB1 1TPH><FfootF><B2B><IBristolI><G 884880 G>
<A2A><HBristolH><ESEE><CM4C><D40kmD><FcarF><B6B><ISwindon I><G 884900 G>
<A6A><HSwindonH><EEE><CM4C><D90kmD><FcarF><B5B><IReading I><G 884990 G>
<A5A><HReadingH><ENE><CM2C><D10kmD><FcarF><B4B><IOxford I><G 884995 G>
<A4A><HOxford H><FfootF><IOX2 6UDI><G 884995 G>

Result

Those tagged lines are the machine-readable version of the optimum route from B1 1TP to OX2 6UD starting at 11:30am on September 6th 2001. The obvious next step is to translate them into a human language. That will be dealt with in "Appendix 8: worked translation example"