Module XI : Demand Analysis - II
Lecture : Shortest path finding algorithms (Dijkstra's algorithm)
 

As the name suggests, shortest path algorithm find the shortest path between two nodes in a network. In the case of transportation networks, the nodes may represent points (or locations) from which traffic is produced or to which traffic is attracted. The nodes also represent intersections. The links represents roads or movements. The above description of a transportation network is a very simplistic viewpoint. Interested readers may refer to books on transportation network analysis to gain a insight of how a real-world transportation facility may be represented as a network. Figure 1 shows a typical network representation of a transportation facility.

Figure1: A typical transportation network.

Two shortest path algorithms are most commonly used in transportation network analysis. One is Dijkstra's algorithm and the other is Floyd's algorithm. In the following these algorithms are described in details. The descriptions are largely adopted from Dusan Teodorovic's book on "Transportation Networks: Aqualitaive treatment".

DIJKSTRA'S ALGORITHM

This algorithm is one attempt to find the shortest path from one node to all other nodes in the network. It assumes that the link lengths are always non-negative.

In this method, every node is assigned a label with two components (x, y). A label could either be temporary or permanent. The algorithm stops when all labels are permanent. As will soon become apparent, after completion, the labels give information on the shortest distances as well as the shortest paths from a particular node to all the other nodes. Also a node is referred to being in the open state if its associated label is temporary; it is to be in the closed state if the label is permanent.

Before proceeding further, some of the notation used here are presented.

l(i, j) : length of the link joining node i to node j.

a : node for which we are investigating the shortest paths to all other nodes.

dai : the shortest known path from node a to node i found in the network, so far.

qi : the immediate predecessor node of node i on the shortest known path from node a to node i found so far.

c : the last node to have moved to being in the closed state.

x : x = dai

y : y = qi

The Dijkstra algorithm is comprised of the following 5 steps:

Step 1:The process starts from node. Since the length of the shortest path from node a to node a is 0, then daa = 0. The immediate predecessor node of node a will be denoted by the symbol + so that qa = +. Since the lengths of the shortest paths from node a to all other nodes 1 on the shortest path are unknown, we put
qi = - for all 1 . The only node which is now in a closed state is node a. Therefore we write that  c = a.

Step 2: In order to transform some of the temporarly labels into permanent labels, we examine all branches (c, i) which exit from the last node which is in a closed state (node c). If node i is also in a closed state, we pass the examination on to the next node. If node i is in an open state we obtain its first label dai   based on equation:

1

in which the left side of the equation is the new label of node i. We should note that dai   appearing on the right side of the equation is the old label for node i.

Step 3: In order to determine which node will be the next to go from an open to a closed state, we compare value dai for all nodes which are in an open state and choose the node with the smallest dai. Let this be sdme node j. Node j passes from an open to a closed state since there is no path from a to j shorter than daj. The path through any other node would be longer.

Step 4: We have ascertained that j is the next node to pass from an open state to a closed one. We then determine the immediate predecessor node of node j and the shortest path which leads from node a to node j. We examine the length of all branches (i, j) which lead from closed state nodes to node j until we establish that the following equation is satisfied :

1

Let this equation be satisfied for some node t. This means that node t is the immediate predecessor of node j on the shortest path which leads from node a to node j. Therefore, we can write that qj = t.

Step 5: Node j is in a closed state. When all nodes in the network are in a closed state, we have completed the process of finding the shortest path. Should any node still be in an open state, we return to step 2.

The algorithm described above can also be ussed to find the shortest path between two specific nodes. In this case, the algorithm is completed when both nodes are in a closed state.

Example: Using the Dijkstra algorithm, calculate the shortest path from node a to all other nodes on the transportation network shown in Figure Y1.

Figure Y1

The number next to the network branches shown on Figure Y1 signify the length of each branch. (We should mention that the length of a branch in a network could also, in addition to actual length, stand for travel time or travel expenses or numerous other values).

We start the process of finding the shortest path at node a. Since the length of the shortest path from node a to node a is 0, then daa = 0. The immediate predecessor node of starting node a is denoted by the symbol + so that qa = +. The length of all other shortest paths from node a to all other nodes are for the present unexamined, so for all other nodes * we put dai = ∞ . Since the immediate predecessor nodes of nodes *on the shortest path are unknown, we put qi = - for all *. The only node which is now in a closed state is node a. Therefore, c = a. Next to the node a symbol we put the label (0 , +) and add the symbol ' to emphasize that node a is in a closed state. Ths completes the first step of the algorithm.

After the first step, the transportation network looks like Figure Y2.

Figure Y2.

 

We now move to the second step of the algorithm. By examining the length of all branches leaving node a which are in a closed state we can write:

1

In step 3 we determine which node will be next in line to pass from an open to a closed state. Since dab< dad node b passes from an open to a closed state. In the same manner, since:

1

we can conclude in step 4 that node a is the immediate predecessor of node b on the shortest path, i.e. qb = a.

Now in step 5 we note that there are still many nodes which are in an open state. Therefore, we have to return to step 2. The transportation network looks like Figure Y3 after going through all five steps of the algorithm for the first time:

Figure Y3

 

Let us now return to the second step of the algorithm. The last node to go from an open to a closed state was node b. This means that c = b. When we examine all branches leaving node b going towards nodes which are in an open state, we have:

1

Since dac< daf node c is the next to switch from an open to a closed state. We then determine the immediate predecessor node of node c. Since :

1

then node b is the immediate predecessor of node c and qc = b.

The network still contains many nodes in an open state, so we must once again return to step 2 of the algorithm. After the second time through all 5 steps of the algorithm, the transportation network looks like Figure Y4.

 

Figure Y 4

The third time through the algorithm gives us:

1

Since dad< dae node d is the next node to switch to a closed state. Since:

1

then node a is the immediate predecessor of node d on the shortest path, so qd = a. And now c = d.

The transportation network looks like Figure Y6 after the third time through the algorithm:

Figur Y5

 

Table 2 shows the calculations leading to the shortest paths and determination of the immediate predecessor nodes after going through the algorithm 11 times.

 

Table 2: Calculating the shortest paths and predecessor nodes.
Times through algorithm
Last node in closed state

Branches from last closed node to open nodes
         dai = min [dai, dac + 1 (c, i)]

Next node in closed state
Predecessor node
4
d

dae = min [8, 12] = 8

dag = min [∞, 14] = 14

e
qe = c
5
e
daf = min [13, 15] = 13
f
qf = b
6
f

dah = min [∞, 23] = 23

dai = min [∞, 22] = 22

dag = min [14, 17] = 14

g
qg = d
7
g
dai = min [22, 21] = 21
i
qi = g
8
i

dah = min [23, 27] = 23

daj = min [∞, 29] = 29

dah = min [∞, 27] = 27

h
qh = f
9
h
daj = min [29, 28] = 28
j
qj = h
10
j

dak = min [27, 30] = 27

dal = min [∞, 30] = 30

k
qk = i
11
k
dal = min [30, 30] = 30
l
ql = j

 

The shortest paths from node a to all other nodes in the network are shown in Figure Y7 with immediate predecessor nodes noted after going through the algorithm 11 times.

Figur Y7

 

Note that given all the predecessor nodes the shortest path from node a to any particular node can be easily reconstructed. For example, the shortest path from a to j can be reconstructed in the following way:

From Figure Y7 it can be seen that the immediate predecessor node of node j is node h. Hence "h to j" is a part of the shortest path to j. Similarly "f to h" is a part of the shortest path to h from a. Hence, "f to h to j" is a part of the shortest path to j. Proceeding similarly we can see a to b to f to h to j is the shortest path from a to j. Using similar logic for all other nodes the shortest paths from a to all other nodes can be diagramatically represented as shown in Figure Y8.

Figure Y8