Tag: dijkstra


Finding a shortest path given a timetable

March 4th, 2009 — 5:02pm

Let’s say that you have a timetable for every stop in a city’s public transport system. Each stop has it’s own timetable, that says how many minutes it takes to get to all the stations that you can get to from that line (excluding changes).

An example visualized graph from the timetables.

An example visualized graph from the timetables.

In the example image to the right, you can see a visualization of the input timetables when we want to go from station A to station F. Station C indicates that a change must be made to reach station F.

When we look in our timetable, we will see how long it will take to reach each station on that line. The weights in the graph (the numbers on the edges), indicates how many minutes that will take. When we look in a timetable, we will only see how long it will take to reach another station on that same line. So when we look at the timetable for station A, we will only see how long it will take to reach station B, C and D. To see how long it takes to reach station E and F, we need to look in the timetable for station C, where we’d have to make a change to reach station F.

Let’s assume that we have a database for all the timetables for every station in the city’s public transport system. We have access to a function db(station, time), which, given a station and a time, returns a list of all the stations that you can reach from the specified station, and how many minutes it will take from the specified time. So when going from station A to station F, the time we need to calculate is the time to get from station A to station C, and then add the time to get from station C to station F, since it’s another line.

One way to find (one of) the shortest paths is to convert the timetables into a graph with the correct weights on them (the weights is the number of minutes between two stations, instead of between that station and the start station), and then using Dijkstra’s algorithm to find the shortest path.

Below you can see the pseudo code for the conversion of the timetables into a graph and then Dijkstra’s algorithm, copied right from wikipedia, and lastly a function that calculates the time it will take. A change between two lines is assumed to take one minute (walking from one train/bus/etc. to another).

Convert the timetables into a graph using Depth-first search.
Time complexity: O(|V| + |E|)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Convert the problem to a graph problem using DFS.
// Graph: The graph to be constructed. Empty graph from the beginning.
// start: The staion/node to start from.
// time: When to start the journey.
// prev: Previous station; used to calculate if a change must be made.
function init(Graph, start, time, prev):
    list := db(start, time)
    if start not in Graph:
        Graph.add(s)
 
    for x in list:
        if x not in start.nbors():
            // A change has not been made, so subtract the time it took to
            // get to the previous stop.
            if prev is in db(x, time):
                start.add_nbor(x[0], x[1] - prev[1])
 
            // A change has been made and the time has been reset.
            // Add one minute for the time it takes to make the change.
            else:
                start.add_nbor(x[0], x[1] + 1)
 
        if x is not in Graph:
            init(Graph, x, time + x[1], start)

Next is Dijkstra’s algorithm, which you can read about at wikipedia if you like. It finds one of the shortest possible routes from one node to another, and returns a list of those nodes. Since every node is inserted into a min-heap in this implementation of Dijkstra’s algorithm, the time complexity will increase with O(nlogn), since we do n insertions (n nodes/stations), and each insertion into a heap takes O(logn) time.
Time complexity: (nlogn + |V|^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 'Graph' is the grapth created with init(), 'start' is the start vertex,
// 'target' is the target vertex to get to and 'time' is the desired time
// to start the journey at. x[0] is the stop, x[1] is the time to get there
// from 'start'.
function dijkstra(Graph, start, target, time):
    Q := empty min-heap
    for x in Graph:
        dist[x] := infinity
        prev[x] := undefined
        Q.add(x)
 
    dist[start] := 0
    while Q is not empty:
        u := Q.pop()
 
        // We can stop here if u is target.
        if u is target:
            calculate_time(Graph, time, dist, target)
            return
 
        for x in u.nbors():
            alt := dist[u] + x[1]
 
            if alt < dist[x]:
                dist[x] := alt
                prev[x] := u

Lastly is the function that will calculate the time it takes to reach the specified station.
Time complexity: O(n)

1
2
3
4
5
6
7
8
9
10
// Calculates the time that the journey will take, including changes.
function calculate_time(G, time, dist, u):
    i := dist[u]
    // Go through and add all distances together.
    while prev[u] is defined:
        u := prev[u]
        i := i + u[1]
 
    // Print the number of minutes one of the shortest distances takes.
    print i

The final time complexity for this will be O(nlogn + n + |V| + |E| + |V|^2)

1 comment » | code, Uncategorized

Back to top