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

# 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.

# 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