TFL JOURNEY PLANNER
PY5
Contents:
Part 1 : The Graph Theory …………………………..……………… page 3
Graphs
Edges
Weighted graphs
Paths
Exercises
Part 2 : Dijkstra’s Algorithm ……………………………………… page 10
Ordering label
Permanent label
Working label
Tutorial
Exercise
Part 3 : Coding & the Project ………………………………………page 19
Project aim
Data structure
Coding Dijkstra’s algorithm
The competition
Team Members:
•
Leah Al-Halaseh (Team Leader)
•
Gordon Cheng (Documentation Leader)
•
Octav Rusuleanu
•
Amir Dhada
•
Minttu Alakuijala
Part 1 Graph Theory
What is a graph?
A graph is a data structure (a way of organising and structuring data for later use and
manipulation) which consists of two main components: a set of “nodes” (also called
“vertices”) and a set of edges (also called “arcs” or “links”). An edge is a connection
between two nodes and is represented by a straight or a curved arrow.
Visual example of a graph:
!
In the above example, the nodes are: a, b, c, d; while the edges are: (a,b), (b,a),
(b,c). Therefore, the set of nodes is {a, b, c, d} and the set of edges is {(a,b), (b,a),
(b,c)}.
The general notation for a graph is: G = (N, E)
“G” is the name of the graph
“N” is the set of vertices
“E” is the set of edges
For the above example, N = {a, b, c, d} and E = {(a,b), (b,a), (b,c)}.
What is an undirected graph?
An undirected graph is a graph in which for every edge that goes from a node x to a
node y, there is also an edge that goes from y to x. This means that if (x, y) is an
edge which belongs to the set E (see above
notation), then the edge (y, x) must also belong to
the set E.
In this example, the graph is NOT undirected
because there is an edge from b to c, but there is no
edge from c to b.
However, adding the missing edge (i.e.: (c, b)) to
this graph would make it undirected, because all
other edges ((a, b) and (b, a)) respect the necessary
conditions.
Note: When undirected graphs are shown as visual diagrams, arrows are dropped
from edges, understanding that each edge can be taken on either direction.
Example of an undirected graph:
!
Here, N = {a, b, c, d} and E = {(a, b), (b, c), (c, d)}
Note: (a, b) is the same as (b, a), (b, c) is the same as (c, b) and (c, d) is the same
as (d, c).
What is the weight of an edge?
Edges can also have a weight (and usually have). The weight can be any natural
number, bigger than 0. Since an edge is a connection between two vertices (let’s
say, x and y), then the weight of an edge is interpreted as being the cost of going
from x to y. “Cost” is an abstract notion, so it can refer to any type of measurement
(e.g.: time, distance, fuel etc.).
In an undirected graph, since an edge from node x to node y is the same as the
edge from y to x, the weight (or cost) of (x, y) will be equal to the weight (or cost) of
(y, x).
Notation: “c(x, y)” means the cost of the edge from x to y.
Consequence: in an undirected graph, c(x, y) = c(y, x).
Visual examples of weighted graphs:
!
The graph on the left is an undirected weighted graph, while the graph on the right is
a directed weighted graph.
What is a path?
A path of length n in a graph is a sequence of nodes x
0
, x
1
, …,x
n
, where each
(x
i
, x
i+1
) belongs to E, for all i between 0 inclusive and n exclusive.
!
In the above graph, paths are: {a, h}, {a, b, c, d}, {e, f, g, b, c, d} etc.
Note: {a, h, g} is not a valid path since there is no edge from h to g.
What are a connected and a strongly connected graph?
A graph is strongly connected if for every pair x, y of nodes in N, there is a path
going from x to y.
A graph is connected if ignoring edge directions, every pair of nodes is connected
through a path.
!
The above graph is connected, but is not strongly connected, since there is no path
from vertex h to vertex a (actually, if you look closer, there is no path from h to any
other node whatsoever).
What is the shortest path from one node to another in a graph?
The concept of a shortest path exists only in weighted graphs. The shortest path
from a node x to a node y is the minimum cost of edges, required to get from x to y.
If there is no path at all from x to y, then there is no shortest path between x and y.
Example: in the graph on the left, take the starting node to be a. The shortest path
from a to d is {a, e, d}, because the cost of the edge (a, e) is 10 and the cost of the
edge (e, d) is also 10. As a result, taking the path a -> e -> d results in a total cost of
20, opposed to the path a -> d, which costs 100 (the weight of the edge (a, d) is
100).
Example: take the same graph and the same starting vertex a. The shortest path
from a to b is a -> c -> b, because c(a, c) = 30 and c(c, b) = 5, thus the total cost is
35, opposed to c(a, b) = 50. Another valid path is a -> e -> d -> b, but c(a, e) = 10,
c(e, d) = 10 and c(d, b) = 20, resulting in a total cost of 40 (10+10+20), which is still
higher than 35.
Note: writing a path as “{w, x, y, z}” is the same as writing “w -> x -> y -> z” or
“{(w, x), (x, y), (y, z)}”.
How to determine the shortest path between two vertices?
In the following lessons you will learn an algorithm which always correctly
determines the shortest path between any two vertices. For now, here are some
ideas to consider:
•
Firstly, determine all the paths between the two nodes, together with their
cost. Then pick the smallest one (in terms of edge cost/weight).
Is this an efficient method though?
•
Start with the initial node. Pick the edge with the smallest cost which starts
from the node. Repeat the process for the vertex which the edge leads to.
Stop when you get to the target vertex.
Does this method work in every case though?
•
Other ideas to consider!
Exercises
1. Draw a graph on a piece of paper, given the following information:
- The graph is directed
- N = {a, b, c, d, e, f, g, h}
- E = {(a, b), (b, c), (a, h), (g, b), (g, h), (f, g), (e, d)}
- The graph is not weighted
2. Take the previously constructed graph and add the following costs:
- c(a, b) = 1, c(b, c)= 1, c(a, h)= 9; c(g, b)= 3; c(g, h)= 5; c(f, g)= 7; c(e, d)= 3
What is the cost of the following paths?
- a -> b -> c ?
- f -> g -> b -> c ?
- f -> g -> h ?
3. Consider the undirected graph in the next page:
What are the shortest paths (and their respective costs) between:
i. b and d;
ii. c and g;
iii. a and f;
!
Part 2 Dijkstra’s algorithm!
Ordering
Label
Permanent
Label
Working Label
The ordering label is assigned once the
vertex has been visited, we start from one
and increment by one.
The permanent label is assigned once the
ordering label has been assigned, it takes
the value of the smallest working label. It
shows you the cost of visiting that vertex
from the begging vertex.
The working label can also be called a
temporary label. It shows the cost, in this
case time, to get to that node from the
beginning, it can change as the algorithm
goes on.
We set Westminster’s ordering label as
one as we start from there hence it is
the first visited. It gets a working label
of zero as there is no time taken to go
nowhere from Westminster, as this
cannot change we also give it the
permanent working label of zero.
Now we calculate the cost, in time, to
get to the station which has a direct
edge and is no more than one stop
away.!
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
1 0
0
1 0
0
4
2
3
We now pick the station which has the
lo west co st, in th is case i t i s
Embankment. So it gets the ordering
label of two, as the previous station
had one, and the permanent label of 2
as that is the cost from Westminster.
Now we visit all the unvisited vertices
tha t a re d ir ectly c onn ec te d t o
Embankment and only one stop away,
in this case it is Charing Cross, so we
fill in the cost for it which is three. Now
we arbitrary pick the vertex with the
lowest temporary label that hasn't been
added, in this case we picked Charing
Cross. We could have also pick Green
Park, it wouldn't have made a
difference to the final answer. We do
same as before setting the ordering
label to three. !
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
1 0
0
4
3
2 2
2
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
4
3
1 0
0
2 2
2
3 3
3
We now visit all the unvisited vertices
with the same conditions as before. So
now Leicester square and Piccadilly
circus have the temporary label of five.
We now add the vertex which doesn't
have a ordering label, in this case it is
Green park. So it get the value of four
and the permanent label of three.
We look to see if any of the vertices
connected to Green park have not
been visited, which are Bond street
and Oxford circus. We also look to see
if any of the vertices connected to
Green park has a lower cost then it has
currently, in this case it is Piccadilly
circus which now has the temporary
label of four.
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
1 0
0
2 2
2
4
3 3
3
3
5
5
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
1 0
0
2 2
2
3 3
3
5
4 3
3
4
5
5
5 4
Now we arbitrary pick one of the
vertices with the temporary value of
four, as this is the least number. In this
case we picked Victoria, so we give it
the ordering label of five and check all
the vertices around it to see if they can
be undated. We do the same for
Piccadilly circus.
Now we do the same thing as before,
picking Bond street as our next vertices
so the order label becomes severn. We
have a look at the connected edges to
see if we can update any of the
temporary labels and we cannot so we
move on to the next vertices with the
lowest temporary label. In this case it is
Oxford circus so it gets a order label of
eight.
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
1 0
0
2 2
2
3 3
3
5
4 3
3
5
5
5 4
4
6 4
5 4
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
1 0
0
2 2
2
3 3
3
4 3
3
5 4
4
7 5
5
8 5
5
5
6 4
5 4
Now we see if we can update the
temporary label of any of the vertices
that is an edge of Oxford circus, we
can update Tottenham court road’s
temporary label. It becomes severn as
the cost is severn from the start.
We now look for the least temporary
value for a vertices that hasn't been
assigned a order label. In this case it is
Leicester square, it gets a order label
of nine.
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
1 0
0
2 2
2
3 3
3
6 4
5 4
5 4
4
4 3
3
7 5
5
8 5
5
5
7
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
1 0
0
2 2
2
3 3
3
6 4
5 4
5 4
4
4 3
3
7 5
5
8 5
5
7
9 5
5
We look to see if we can update any of
the vertices that have an edge to
Leicester square, in this case it is
Tottenham court road, we cross the
previous temporary label out.
W e c a l c u l a t e t h e c o s t f r o m
Westminster to Tottenham court road to
be six, so we write this as its temporary
value.
As Tottenham court road is the last
vertices without a order label we give it
one of the value ten. Now all of the
vertices has a permanent value and a
order label. So we can start working
backwards.!
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
7
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
10 6
7 6
Tottenham Court Road to Westminister:
We start from Tottenham court road and
work backwards towards Westminster. We
see if the permanent label minus the cost
of the edge is equal to the permanent able
of the vertices. In this case Leicester
square is equal, as six minus one is five.
And Oxford circus is not as six minus two
is not five.
So we head down Leicester square and
repeat what we did before. Five minus two
is three not four so we go to Charring
cross.
!
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
7
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
10 6
7 6
!
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
7
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
10 6
7 6
We repeat this again and we get three
minus one is two and three minus two is
one which is not equal to four. So we know
that Embankment is the next vertices.
W e r e p e a t the s a m e t h i n g fr o m
Embankment but in this case we only have
one way to go. Two minus two is zero
hence Westminster is the next vertices.
!
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
7
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
10 6
7 6
!
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
7
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
10 6
7 6
Congratulations, we have found the
shortest path from Westminster to
Tottenham court road. We go from
Westminster to Embankment to Charing
cross then to Leicester Square and finally
Tottenham court road. This takes a total
time of 6 minutes. Also note that if we had
two edges that satisfy the equation we
could have arbitrary picked one.
Now it’s your go!
Find the shortest path from Green Park to Charing Cross using the method shown above.
!
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
7
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
5 4
4
1 0
0
2 2
2
3 3
3
6 4
5 4
4 3
3
9 5
5
8 5
5
7 5
5
10 6
7 6
Oxford Circus
Tottenham Court
Road
Leicester Square
Piccadilly Circus
Green Park
Bond Street
2
1
2
2
2
1
2
1
Embankment
Westminster
Victoria
2
4
2
2
3
2
1
Charing Cross
Part 3 Coding & the Project
To put all your knowledge about graphs and shortest path algorithms into practice, you will
be doing an exiting programming project! You will be creating your own version of the
Journey Planner, just like the one from TfL (http://tfl.gov.uk/plan-a-journey/). Your version
of the Journey Planner should be able to take in two stations (origin and destination) from
the user, and display the shortest path (all stations on the path, in order) and the total time
needed for that journey.
All students should be aiming to:
•
Create a simple command line interface for input and output.
•
Write code that can print out a path between two stations.
Most students should be aiming to:
•
Implement a data structure that can effectively represent a graph.
•
A correct implementation of Dijkstra’s algorithm to find the shortest path between two
stations.
Some students should be aiming to:
•
Improve on the data that has been provided to achieve better results.
•
Add in extra features to the data structure, algorithm or user interface to improve the
overall user experience of the program.
At the end of these lessons, a competition will be held where the program each of you
wrote will be put against each other to see whose program produces the most accurate
result when compared to the TfL Journey Planner!
Breaking Down the Problem
Dijkstra’s algorithm might be a more complex algorithm than ones you have learned or
written. The best way of turning an algorithm like this into code is to first break down the
problem into smaller problems. This is sometimes called top-down design.
The final program you write should work as follow:
Asks the user to input the origin and destination stations.
Evaluate the shortest path.
Display the path and the total time.
From this, it is clear that the program should first be split up into 3 sections; input,
evaluate, and output.
Input
Getting two strings (one for the origin and one for the destination) using print() functions
should be an easy task so we won’t dwell in it. However, one thing to think about is data
validation. What if the user enters a station that is not in the dictionary? What about upper
and lower cases?
Output
There are multiple ways you can print out the path in the end, and it depends on how you
plan to store the path once it has been evaluated. The simplest way is to use a list, where
strings of station names in the path are stored in order. This list can then be displayed
using a simple for loop. Also, do not forget that you will need to display the total time it
takes to get from the origin to the destination.
In the end, you will need a list that contains the path and an integer which contains the
total time. So the evaluation section will need to produce that, but how?
Evaluate
We have considered the input and the output, now we just need to be able to actually
evaluate the shortest path. Since Dijkstra’s algorithm turns out to be quite a complex
algorithm, the most sensible thing to do is to break down the problem even further.
Data Structure
Before you start programming the Dijkstra’s algorithm, you need to create a data structure
that represents the graph which the program would use to perform the algorithm on. There
are many ways of doing this, and the choice depends on the programming language you
are using and also your personal preferences. However, for this project, we will focus on
one type of data structure - dictionary.
You should be familiar with Python lists as a sequence data structure. A list can contain
multiple elements which can be accessed with an integer index, starting from 0 for the first
item, 1 for the second item, and so on.
A dictionary works similarly to a list, but instead of having integer indexes for each
element, elements in a dictionary are indexed by keys, which can be of type string,
number, and other immutable types. You can think of it as a real dictionary, where all the
definitions (the elements) are indexed by the words defined by the definitions. Therefore,
every element in a dictionary must have both a key and a value; this is denoted as key :
value.
roman = {“one”: “I”, “five”: “V”, “ten”: “X”, “fifty”: “L”}
In the example above, the dictionary roman is defined with multiple key:value pairs that
represents the roman numerals. Note that dictionaries opens and ends with a curly bracket
and each key:value pair are separated by a comma. To access the elements in a
dictionary, you can use the square bracket syntax, just like with lists.
roman_ten = roman[“ten”] # roman_ten now has the value “X”
Also, just like you can put lists within lists, you can also put dictionaries inside dictionaries!
This can be extremely useful for our use case, as shown below.
graph = {“Euston Square”: {“Baker Street”: 5, “Kings Cross”: 2}}
The dictionary graph is declared with one element with the key “Euston Square” which is a
dictionary with two elements; one with the key “Baker Street” and has the value 5; the
other has the key “Kings Cross” and a value of 2. The number values here are
representing time in minutes. You can access the elements just like you would with lists
that has lists as elements.
euston_sq_to_kings_x = graph[“Euston Square”][“Kings Cross”]
# euston_sq_to_kings_x now has the value 2
The graph dictionary can be expanded to include all vertices of the graph that represents
the underground network.
graph = {
"Aldgate East": {
"Liverpool Street": 4,
"Tower Hill": 2
},
"Baker Street": {
"Bond Street": 2,
"Edgware Road": 3,
"Euston Square": 5,
"Oxford Circus": 4
},
"Bank": {
. . .
},
. . .
}
You can also iterate through a dictionary just like lists. The following code will print all the
top level keys.
for station in graph:
print(station)
However, if you ran the code above, you may have noticed that it does not print it out in
the order that was given in the declaration of the dictionary. This is because elements in a
dictionary are not ordered so when you iterate through it, it will still go through all
elements, just not in the order you would expect it to.
A dictionary that includes 30 zone 1 stations (based on the graph shown above) is made
available to you, but you may want to add and modify the dictionary so it includes all zone
1 stations. Information on the average travel times between adjacent stations is available
on the Transport for London website.
NB In the dictionary provided to you, Kings Cross St Pancras station is simply called Kings
Cross and Bank/Monument station is represented as a single station named Bank.
Dijkstra’s Algorithm
What you should be familiar with before starting to code:
•
graph theory
•
lists
•
dictionaries
•
Dijkstra’s algorithm
Dijkstra’s algorithm may be more complicated than other algorithms you may have
programmed. If you think you are familiar with both the algorithm and the fundamentals of
Python programming, it can be much more beneficial for you to just try programming the
algorithm yourself. However, if you think you’re not confident enough to take on this big
challenge, read on for some hints and detailed instructions on programming the algorithm.
GUIDE TO PROGRAMMING DIJKSTRA’S ALGORITHM
You’re going to see an example program written in pseudocode. Pseudocode is not real
code - it’s meant to be read by humans instead of computers. Rather than being in any
real programming language, pseudocode is written just to communicate ideas.
We are not giving you any Python code, because we want you to write it yourself.
Read through Dijkstra’s algorithm in pseudocode to get an idea for how to structure your
Python program. The algorithm is first explained in five parts, which, when put together,
form the complete program.
Part 1
The first thing we need to do is initialise a few data structures.
i) A list visited will contain the vertices that we have gone through in the algorithm.
ii) The dictionary distance will contain for each station the shortest distance (distance in
this case, is measured in time) from the start point.
iii) The dictionary predecessor will contain for each station the previous station we need to
go through to get this shortest distance.
iv) The variable current will contain the vertex we are currently working at.
dijkstra(tubemap, origin, destination)
# initialise:
empty list visited
empty dictionary distance
empty dictionary predecessor
current = origin
predecessor of current = None
distance of current = 0
Part 2
Secondly, we need a loop in which we will visit each vertex at a time. This loop will
continue running until each vertex has been visited.
Note: by “visiting” a vertex we are not adding it to the route, only looking at it in the context
of Dijkstra’s algorithm, similar to filling out the permanent label of a vertex on paper.
while the length of visited is less than the length of tubemap
# loop until every vertex has been visited
add current to visited
Part 3
The following code will go inside the loop. For each vertex current that we visit, we need to
look at all its unvisited neighbouring stations, and calculate the distance from the starting
point to these neighbouring stations through current. Just like we did on paper last time.
If the neighbouring (or adjacent) stations already have a shorter distance calculated for
them, we do not want to replace the entry of that station in the dictionary distance with a
bigger value.
# look at each station adjacent to the current station
for adjacentStation in tubemap[current]
if adjacentStation is not in visited
newDistance = distance of current + graph[current][adjacentStation]
if adjacentStation has an entry in distance
if newDistance < distance of adjacentStation
# replace old value for distance from origin with new one
distance of adjacentStation = newDistance
predecessor of adjacentStation = current
else
# if a previous distance from origin to adjacentStation has not been
# calculated, save new distance
distance of adjacentStation = newDistance
predecessor of adjacentStation = current
Part 4
After we’re done with vertex current, we’ll go through all unvisited stations that we have
calculated a distance for, and choose the vertex with the smallest distance to be the next
one we visit.
# initialise:
minimumDistance = some large value (e.g. infinity)
# so that we can find the smallest entry in distance by comparing entries to
# minimumDistance
for each station in distance
if station is not in visited and distance of station < minimumDistance
minimumDistance = distance of station
current = station
# the unvisited station with the smallest distance will be the next vertex to
# visit
Part 5
We have gone through all vertices! So… what now?
This is where the dictionary predecessor comes in. We now know:
1) the shortest distance to every vertex
2) the predecessor of every vertex on the path that we need to follow to get this shortest
distance
All we need to do is take the predecessor of our destination, again the predecessor of that
station, and so on, until we get back to the start. We now have the shortest path! Right
after we reverse the path.
We can print out the results in the end.
# initialise:
empty list path
nextStation = destination
while nextStation != None
add nextStation to path
nextStation = predecessor of nextStation
reverse path
print path
print “This journey takes ”, distance of destination, “ minute(s).”
On the next page is the complete program without any comments. It’s 40 lines long, which
may seem like a lot, but you already know the algorithm and have looked at it in parts. If
anything is unclear with the structure, go back and read the comments and explanations
about each of the parts.
dijkstra(tubemap, origin, destination)
empty list visited
empty dictionary distance
empty dictionary predecessor
current = origin
predecessor of current = None
distance of current = 0
while the length of visited is less than the length of tubemap
add current to visited
for adjacentStation in tubemap[current]
if adjacentStation is not in visited
newDistance = distance of current + graph[current][adjacentStation]
if adjacentStation has an entry in distance
if newDistance < distance of adjacentStation
distance of adjacentStation = newDistance
predecessor of adjacentStation = current
else
distance of adjacentStation = newDistance
predecessor of adjacentStation = current
minimumDistance = some large value (e.g. infinity)
for each station in distance
if station is not in visited and distance of station < minimumDistance
minimumDistance = distance of station
current = station
empty list path
nextStation = destination
while nextStation != None
add nextStation to path
nextStation = predecessor of nextStation
reverse path
print path
print “This journey takes ”, distance of destination, “ minute(s).”
If you get stuck at programming Dijkstra’s algorithm (or any algorithms for that matter), it
may be beneficial to discuss your problems and ideas with a friend. Explain what you’ve
got so far and what you’re currently stuck on. Sometimes this may due to the tiniest error
in your code and you’ll be surprised as to how much another pair of eyes can see from
your code!
Improving Your Results
By now you should have a program that can figure out a shortest path between two
stations. but if you compare your results with actual results from TfL Journey Planner (as
you should have…), you would have found that your results are not very accurate. So how
can you improve on the results?
Intermediate stations
You have been provided with a dictionary that contains data for 30 stations in zone 1, most
of which are interchange stations. There are approximately 30 more zone 1 stations, you
may want to add data for these station to the dictionary.
Data accuracy
The travel times in the dictionary provided to you are all rounded to the nearest minute. Is
that accurate enough? Considering that some of these times is 1 - 2 minutes, a 30 second
difference in time would seem to have a significant impact on the accuracy of the overall
results. Getting more accurate data from TfL may improve your results.
Transfer times
Take the journey from Victoria to Bank, by the diagram shown previously (which the
dictionary is based on), the shortest route is getting the Victoria line to Green Park, change
for the Piccadilly line to Holborn, and finally change for the Central line to Bank. However,
if you input that journey into TfL Journey Planner, it will (for most of the time) give you a
different result. Their suggested route is to take the Victoria line to Oxford Circus and
change once to the Central line towards Bank. This is probably because TfL Journey
Planner favours routes that requires less transfers between lines as walking from one
platform to another takes (a surprisingly long) time. So how can your program take this into
account?
At the moment, all lines going through one particular station shares one vertex so the
graph does not fully represent the actual situation, after all, the train you’re travelling on
wouldn’t magically change lines when arriving at an interchange station. The obvious
solution to this is to have a separate vertex for each line at every station and add edges
between these vertices to represent the transfer times. Unfortunately, while travel time
between stations is readily available on the internet, transfer times are not so you just have
to make your best guesses.
However, this poses a new problem as now you have multiple vertices for one station, how
will you program know which to start and finish if the origin or destination station is one of
these interchange stations?
The Competition
Now that all of you have finished your program, it’s time to put them against each other.
The competition is very simple, your teacher will say an origin-destination pair and you will
need to input that into your program and record the result. Your teacher will then input the
pair into the official TfL Journey Planner (set to Tube only). If your shortest route matches
any one of the routes shown in the result page of the TfL Journey Planner, you get to stay
on to compete in the second round; otherwise, you’re out. The program which fails last will
be the winner.
•
The origin-destination pairs will get progressively tricky, so test your program with tricky
routes!
•
Make sure your teacher sets the Journey Planner to Tube only!
•
All origin-destination pairs will consist of zone 1 stations only.
Example journeys
Here are some example journeys that you can use to test your program, the shortest
journey time according to the map/dictionary we provided to you is noted in brackets.
1. Edgware Road -> South Kensington (13)
2. Euston Square -> Elephant & Castle (17)
3. Euston Square -> Waterloo (14)
4. Notting Hill Gate -> London Bridge (18)
5. Paddington -> Liverpool Street (20)
6. Paddington -> Elephant & Castle (19)
7. South Kensington -> Aldgate East (20)
8. South Kensington -> Kings Cross (13)
9. Westminster -> Tottenham Court Road (6)
If you are confident with your program, test it with more accurate information from TfL
Journey Planner.
