A Study on Different Algorithms for Shortest Route Problem

A Study on Different Algorithms for Shortest Route Problem

Dr. Roopa, K.M., Apoorva, H.R1., Srinivasu,V.K.2 and Viswanatah, M.C 3

Abstract

Shortest path problems are among the most studied network flow optimization problems with interesting application across a range of fields. In this paper, three shortest path algorithms are discussed viz. Dijkstras Algorithm (one to all pairs of nodes), Floyd Warshalls Algorithm (all to all pairs of nodes) and Linear Programming Problems (LPP). These algorithms are also solved using Matlab software, which gives quick results for larger nodes. This paper also deals with the methodology to find shortest distance using the dual of Linear Programming Problems. In addition, Complementary Slackness Theorem is discussed to solve the primal problem from the solution of dual problem and determine the shortest distance as well as shortest routes.

Key Words: Shortest Path, Dijkstras Algorithm, Floyd Warshalls Algorithm, Linear Programming Problem, Algebraic Method, Matlab

1.0 Introduction:

Finding the shortest path is an important task in network and transportation related analysis. Shortest distance problems are inevitable in road network applications, such as city emergency handling and driving system, where optimal routing has to be found. Therefore, network optimization has always been the heart of operational research. Also, as traffic conditions of a city change from time to time, there could be a huge amount of request occurring at any moment, for which an optimal path solution has to be found quickly. Hence, efficiency of an algorithm is very important to determine the shortest routes are between nodes in a network.

There are many algorithms that can be used to determine the shortest route between two nodes in a network. In this paper, two standard algorithms Dijkstras algorithm [1], [4] and Floyd Warshalls algorithm are discussed and also solved using Matlab software. The linear programming formulation of shortest route problem solved using (0-1) binary integer programming technique is also discussed. The dual of formulated linear programming and shortest route problem [2] solved by algebraic method is demonstrated for small number of nodes, as it is difficult to solve for large number of nodes. In such cases, Matlab software can be the best choice. Further, the shortest distance and shortest route determined using Complementary Slackness Theorem [5].

1. Dijkstras Algorithm:

   Let G = (N, A), where, N = (1,2,3..n) is a node, be a weighted and directed network in which the weight of the every directed arc (edge) is non negative. Dijkstras algorithm is used to find the path with minimum weight from a chosen vertex, say vertex 1, to any other vertex s of G. This algorithm is iterative in nature and each of these iterations consists of two steps to calculate the shortest distance. Further, the algorithm provides means to trace the shortest path accordingly.

2. Outline of Dijkstras Algorithm:

Dijkstras algorithm considers two sets: i) set P, which at any specific point consists of all the nodes that were encountered by the algorithm and ii) set S, a precedence set, which at any specific point consists of the precedent node for each node in the network. Apart from these sets, the algorithm utilizes the following distance information.

qij,for i, j=1, 2, 3, 4n and ij, denote the weight of the directed edge (arc) from vertex i to vertex j. If there is no arc from i to j, then is set to be infinity.

tj, for j=1, 2, 3, 4n and js where s is the start index. Also,

tj = q1j for j=2,3,4n (1)

In each iteration, the sets P and S as well as the set of all tj, for j=1, 2, 3, 4n and js, that are output from the previous iteration are taken as inputs.

Initially P = {s}. S is a set of size n populated with i) 0 if tj = infinity, ii) s if tj = finite value The steps involved in each iteration for finding the shortest distance are summarized below: Step 1: Identify minimum among the computed values. Let tk be the minimum.

Add k to the set P.

Step 2: Now P = {1, k}. For each of the nodes not in P and with finite qkj, for j=1, 2, 3, 4n and j

P, recalculate tj using the below expression:

tj = min{ tj, tk + qkj } (2)

Only if (tk + qkj) < tj, then update the jth entry in S to k.

Continue the iterations until the end node, e, is added to the set P.

Similarly, the steps to trace the shortest path between nodes s and e, using Dijkstras algorithm are given below:

Step 1: Take node e as the last node in the shortest path

Step 2: Find the eth entry in the set S, let this be x. Add this prefix node x to the partially constructed shortest path.

Step 3: Check whether x is equal to s. If so, go to Step 4; else go to Step 3. Step 4: The required shortest path from node s to node e is thus constructed.

Example: Determine the shortest distance and shortest path from vertex 1 to vertex 7 in the weighted, directed network is depicted in a given Fig. 2.1.

17

6

6

5

5

2 7

4

4

15

6 8

1 8 4 6

7

4

10 3 5 2

4

Figure 2.1: The shortest route network

First Iteration: P= {1}, S={0,1,1,0,0,0,0}, and t2 = 15, t3 = 10, t4 = , t5 = , t6 = , t7 =

Step 1: Note that tj is minimum for j=3, i.e., t3 =10 .Therefore add 3 to the set P

Step 2: Now, P={1,3} and t3 =10

t2 = min {t2, t2 + q32} t2 = min {15, 10+ 8} =15

t4 = min {t4, t3 + q34} t4 = min {, 10 + } =17 => S [4] = 3 t5 = min {t5, t3 + q35} t5 = min , 10+4 }= 14. => S [5] = 3

Second Iteration: P= {1, 3}, S={0,1,1,3,3,0,0} , and t2 = 15, t3 = 10, t4 = 17, t5 = 14, t6=, t7 =.

Step 1: For the set of recalculated tj values, minimum occurs at j=5, i.e.t5 =14. Therefore, add node 5 to set P.

Step 2: Now, P = {1, 3, 5} and t5 =14

t6 = min , 14 + 2} =16 => S[6] = 5 t7 =min , 14+8} = 22 => S[7] = 5

Third Iteration: P = {1, 3, 5}, S={0,1,1,3,3,5,5} ,and t2 = 15, t3 = 10, t4 = 17, t5 = 14, t6 = 16, t7 = 22

Step 1: The minimum tj value occurs for j=2 ,i.e. t2 =15. Add node 2 to the set P.

Step 2: P= {1, 3, 5, 2} and t2 =15

No change in the set of tj values.

Fourth Iteration: P = {1, 3, 5, 2}, S = {0, 1, 1, 3, 3, 5, 5}, and t2 = 15, t3 = 10, t4 = 17, t5 = 14, t6 = 16,

t7 = 22

Step 1: The minimum tj value occurs for j=6 ,i.e. t6 =16. Add node 6 to the set P.

Step 2: P = {1, 3, 5, 2, 6} and t6 =16

t7 = min {22, 16+6} =22 => since t7 = (t6 + q67), S [7] remains unchanged.

Fifth Iteration: P = {1, 3, 5, 2, 6}, S= {0, 1, 1, 3, 3, 5, 5}, and t2 = 15, t3 = 10, t4 = 17, t5 = 14, t6 = 16,

t7 = 22

Step 1: The minimum tj value occurs for j=7, i.e., t7 =22. Add node 6 to the set P. Add node 7 to the set P. As the end node, 7, is added to the set P, the process stops.

Thus, the shortest distance between node1 and node 7 = t7 =22 The shortest route is obtained as follows: S={0,1,1,3,3,5,5}and (s ,e)=(1,7).

In order to reach node 7 from node 1, take prefix node as node 5, S [7] = 5. Similarly, to reach from node 1 to node 5 take prefix node as node 3, S[5] = 3. Continuing this process, to reach from node 1 to node 3, take prefix node as node 1, S[3] = 1. As the prefix node, in this step, is same as the start node, this process stops. Thus, the shortest route is 1357 which is of distance 22 units.

Other alternate routes from node 1 to node 7 are P={1,3,4,7} , P={1,3,5,6,7} which also givs shortest distance of 22 units.

The Dijkstras algorithm to find the shortest path can also be solved using Matlab software and the corresponding output is given below:

dist =22 ; path =1 3 5 7; pred = 0 1 1 3 3 5 5

Thus, the shortest distance is 22 and shortest path is 1357.

3.0 Floyd Warshalls Algorithm:

Floyd Warshalls Algorithm is a graph analysis algorithm to find the shortest route between any two nodes in a network with positive or negative edge weights with no negative cycle. This algorithm uses the dynamic programming technique to solve the shortest path problem between all pairs of nodes (all to all) in a directed network. It represents the network as a square matrix with n-rows and n- columns and at the end of the algorithm each (i,j) of the matrix gives the shortest distance from node i to node j. If there is a direct link between node i to node j, then the value at (i,j) is finite, otherwise it is infinite, i.e, d .

Floyd Warshalls Algorithm is based on transitivity property. Given three nodes i, j and k are shown in Fig. 2.2.

From the transitivity property,

d (i ,j)+d(j,k)=d(i,k).

j

i k

Figure 2.2: Transitivity Property

The algorithm exploits the above property to find the shortest distance between nodes i and k as follows:

If, d (i ,j)+d(j,k)<d(i,k). Then, it is optimal to replace the direct route from ik, where the indirect route is ijk.

1. Outline of Floyd Warshalls Algorithm:

   The Floyd Warshalls algorithm uses two adjacency matrices i.e, i) distance matrix Dk and ii) precedence matrix Sk, where k=0, 1, 2..n. In first iteration, the algorithm takes initial distance matrix D0 and initial precedence matrix S0 as input. Then on, in each iteration, the distance matrix and precedence matrix that are output from the previous iteration are taken as input. After n iterations, where n is the number of nodes in the distance matrix and the nth iteration gives the optimal/final distance matrix Dk=n as well as the final precedence matrix Sk=n. The optimal distance matrix Dn represents the shortest distances between any two nodes in the network and the corresponding shortest paths can be traced out from the precedence matrix Sn. The steps for shortest distance under Floyd Warshall algorithm are summarized below:

   Step1: Set iteration k=1.

   Step2: Consider first column and first row of the initial representation of distance matrix D0 as pivot column and pivot row and apply transitive operation.

   Step3: If any entry of the pivot column or pivot row is infinity then row corresponding to this element need not be considered.

   Step 4: There are two cases:

   Case (a): If the condition d (i ,k)+d (k ,j) <d (i ,j) ( i k , j k , i j) , make the following changes

   1. Create Dk by replacing d (i, j) in Dk-1 with d (i, k) + d (k, j)

   2. Create Sk by replacing Sij in Sk-1, set k=k+1 and repeat step k up to n steps .

Case (b): if d (i ,k)+d(k ,j)=d(i ,j) ( i k , j k , i j); do not to make any changes, this implies that ikj is an alternate route for ij.

Similarly, the steps to trace the shortest path between two nodes, say i and j using Floyd-Warshalls algorithm are given below:

Step 1: Take node j as the last node in the shortest path.

Step 2: Find the value S [i, j] from the precedence matrix Sn, let it be x. Add this Prefix node x t partially constructed shortest path.

Step 3: Check whether x is equal to i. if so, go to step (4); else, set j = x and go to the step 3 Step 4: The required shortest path from node i to node j is constructed.

Example: Determine the shortest distance and shortest paths between all pairs of nodes in a transportation network as shown in Figure 2.1.

Iteration (0): Consider the initial representation of the matrix D0 and S0, as shown in fig 2.1. d (i, j) = , implies no traffic is allowed from node i to j.

3

Iteration (1): Set k=1. Consider the first column and first row of D0 as pivot column and pivot row respectively. As all the entries of the pivot column in D0 are infinity, D1 and S1 are same as D0 and S0 respectively.

Iteration (2): Set k=2. Consider second column and second row of D1 as pivot column and pivot row respectively. Except d (1, 2) and d (3, 2), all the entries in the pivot column are infinity. Also except d (2, 4) and d (2, 7), all the entries in the pivot row are infinity. Now apply transitivity property to obtain the following results:

(i) d(1,2)+d(2,4)= d(1,4) d(1,2)+d(2,7)=d(1,7)

But, d(1,2)+d(2,4)=15 + 4 and d(1,4) = But, d(1,2)+ d(2,7)= 15 + 17 and d(1,7)=

This implies , then d (1, 4) =19 this implies , t hen d (1, 7) = 32

Similarly, 12>7, then d (3, 4) = 7 and , then d (3, 7) = 25.

Observe that there is no change in the value of d (3, 4) = 7. So, it cannot be improved.

(ii) The precedence matrix S1 can be changed as

S (1, 4) = 2, S (1, 7) = 2 & S (3, 7) = 2. These are the changes shown in the matrix D 2and S2

Iteration (3): Set k=3. Consider third column and third row of D3 as pivot column and pivot row respectively. Except d (1, 3), all the entries in the pivot column are infinity and also except d (3, 5) and d (3, 7), all the entries in the pivot row are infinity. Further, apply transitivity property to obtain the following results:

(i) Since, d(1,4)=17 , d(1,5)=14 and d(1,7)=32 . So, d (1,7) = 32 cannot be improved .

(ii) Set precedence matrix S2 as S (1, 4) = 3, S (1, 5) = 3. The changes are as shown in the matrix D3 and S3

Continuing in this way, the final matrix in the last iteration where none of the entries in the d (i,j) can be improved by transitivity property, because all the elements in the last row are infinity.

Finally, the shortest distance between any two nodes is determined from the matrix D7.

Next to find the shortest path between nodes, say 1 and 7 i.e (i ,j)=(1,7). In order to reach node 7 from node 1, take prefix node as node 4, S7 [1, 7] = 4. Similarly to reach from node 1 to node 4 take prefix node as node 3, S7 [1, 4] = 3. Continuing this process to reach from node 1 to node 3, take prefix node as node 1, S7 [1, 3] = 1. As the prefix node, in this step, is same as the start node, this process stops. Thus, the shortest route is 1347, which is of distance 22 units. Similarly, other possible shortest routes can be calculated from the matrix D7 and S7.

The Floyd Warshalls algorithm to find the shortest path (all too all pairs of nodes) can also be solved using Matlab software and the corresponding output is given below:

A=inf(7,7); A(1,2)=15; A(1,3)=10; A(2,4)=4; A(2,7)=17; A(3,2)=8; A(3,4)=7; A(3,5)=4;

A(4,5)=4; A(4,6)=6; A(4,7)=5; A(5,6)=2; A(5,7)=8; A(6,7)=6;

>> [S,P,result] = FloydSPR(A,1,7)

Result = 22.

1. Linear Programming Formulation of the Shortest Path Problem:

   Linear Programming is a simple programming formulation problem. Most of the network problems can be formulated as Linear Programming Problems and can be solved using simplex method algorithm. In this section, two Linear Programming formulations for the shortest-route problem are discussed. These formulations are generally used to find the shortest route between any two nodes in the network.

   Formulation 1: This formulation assumes that an external unit of flow enters the network at node s and leaves at node t, where s and t are the two nodes between which the shortest route is to be determined.

   Define, xij = Amount of flow in arc (i , j), for all feasible i and j, cij = Length of arc (i , j), for all feasible i and j.

   Because only one unit of flow can be in any arc at any given time, the variable xij can assumes binary values (0 or 1) only. Thus, the objective function of the linear program becomes:

   Minimize Z = all defined arcs ci,j xi,j,

   The below constraint represents the conservation of flow at each node and for any node j; Total input flow = Total output flow.

   Formulation 2: This formulation is the dual problem of Linear Programming discussed in Formulation1. In the dual problem, the number of variables is equal to the number of nodes in the network. Also, it is equal to the number of constraints in formulation1. Further, all the dual variables must be unrestricted as all the constraints in Formulation1 are equations.

   Let yj be the dual constraint associated with node j. Given that s and t are the source and destination nodes of the network, then the dual problem is defined as follows:

   Maximize Z = yt ys

   Subject to yj – cij for all feasible i and j. However, all yi and yj are unrestricted in sign.

   Example: Consider the problem of determining shortest route in the network as shown in above Fig.

   2.1. Here, s = 1 and t = 7. The below given Fig. 2.3 shows how a unit of flow enters at node1 and

   leaves at node 7.

   Destination

   17

   2 7

   15 6

   Source 4 5

   6 8

   1 8 4 6

   7 4

   10 3 5 2

   4

   Figure 2.3: Network with source and destination

   By setting Xi,j = and then corresponding values of Linear program is listed below:

   Min Z	X12	X13	X24	X27	X32	X34	X35	X45	X46	X47	X56	X57	X67
   	15	10	4	17	8	7	4	4	6	5	2	8	6
   Node1	-1	-1												= -1
   Node2	1		-1	-1	1									= 0
   Node3		1			-1	-1	-1							= 0
   Node4			1			1		-1	-1	-1				= 0
   Node5							1	1			-1	-1		= 0
   Node6									1		1		-1	= 0
   Node7				1						1		1	1	= 1

   From the above table, we obtain the following objective function and constraints of the linear programming problem as given below:

   Min Z = 15×12+10×13 +4×24+17×27+8×32+7×34+4×35+4×45+6×46+5×47+2×56+8×57+6×67

   Subject to -x12-x13 = -1

   x12-x24-x27 +x32 =0 x13-x32 -x34-x35=0

   x24+x34 x45 -x46-x47 = 0

   x35+x45 x56 x57 = 0 (3)

   x46+x56 x67 = 0, x27+x47 + x57 +x67 =1 xij {0,1} for i ,j=1,2,3,4,5,6,7

   The above constraints represent the flow conservation at each node. Therefore, the problem is a binary integer programming problem. After solving this problem using Matlab software, the optimal solution Z=22 at x13 =1, x34 =1, x47 obtained. This solution gives the shortest route from node 1 to node 7 as 1347 and the associated distance is z = 22 units.

   From the concept of dual of the Linear Programming Problem, the following objective function and constraints are obtained:

   Maximize Z =y7 y1

   Subject to yi yj, for all feasible i and j

   y2 y115 (Route 1 to 2), y3 y1 10(Route 1 to 3), y2 y38 (Route 3 to2), y4 y37 (Route 3 to 4),

   y5 y34 (Route 3 to 5), y7 y2 17(Route 2 to 7), y4 y24 (Route 2 to4), y7 y45 (Route 4 to 7),

   y6 y46 (Route 4 to 6), y5 y4 4(Route 4 to 5), y7 y58 (Route 5 to7), y6 y52 (Route 5 to 6), y7 y66 (Route 6 to 7). Where, y1, y2. . .. . y7 are unrestricted in sign.

2. Algebraic Method for solving the dual Linear Programming Problem:

The dual linear programming problem can also be solved using algebraic method for only small number of variables. However, solving the above dual Linear Programming Problem through algebraic method, by introducing slack variables which gives better result compared to any other software packages. The first and final tableaus of algebraic method are given below:

First tableau:

NZV: Non Zero Variables : Objective function with reversed sign Final tableau:

From the above tableau, it is obtained that,y1 =0, y2 =13, y3 =10, y4 =17, y5 =14, y6 =16, y7 =22. The above dual problem can also be solved using Matlab software. The solutions obtained from Matlab software are given below:

y1 = 10.4979, y2 = 3.6415, y3 = 0.4979, y4 = 6.5021, y5 = 3.5021, y6 = 5.5021, y7 = 11.5021

The value of Z = 22 gives the shortest distance from node 1 to node 7. By considering, the solutions that satisfy the above constraints the following routes: 1-3, 3-4, 3-5, 4-7, 5-7, 5-6 and 6 -7 are obtained. From these sequence of routes 1-3, 3-4, 4-7, the shortest route 1347, which is of distance 22 units from node 1 to node 7 is traced. Similarly, other alternate shortest routes that can be obtained are: 1357 and 13567 respectively.

The shortest route can also be determined using Complementary Slackness Theorem [3] & [6]. As the sequence of routes 1-2, 3-2, 2-7, 2-4, 4-6 and 4-5, do not satisfy the constraints in the dual problem, from the Complementary Slackness Theorem it follows that x12=x32 = x24 =x27=x45 =x46 = 0

Substituting these variable values in the primal problem, the following systems of equations are obtained: x13 = 1; x13- x34 x35 =0; x34-x47=0; x35-x56 x57 =0 (4)

x56x67 =0; x47+x57 +x67 =1

By solving above system of linear equations using Gauss Elimination Method, the system in echelon form becomes:

x34+ x35 = 1; x35+ x47 =1; x47+x56 + x57 =1; x47+x57 +x67 =1 (5)

In the above system of equations, there are 4 equations (r=4) with 6 unknowns (n=6) and two free variables (x35, x56,). Hence, the possible choices are: (0,0),(0,1),(1,0),(1,1). Each of these possible choices may or may not be the solution points because the dependent variables have the restriction, = 0 or 1.

For the first choice (0, 0), i.e. x35 =0, x56 =0, by substituting these in equation (5), we get:

x34 =1, x47 =1, x57 =0, x67 =0, x13 =1. Then the shortest route is 1-3, 3-4 and 4-7 i.e. 1347.

Similarly, the third choice (1,0) and fourth choice (1,1) give the shortest routes which are 1357 and 13567 respectively. However, the second choice (0,1) does not give the shortest route because it does not satisfy the equation (5).

5.0 Conclusion:

From the below Fig. 2.4, it is evident that Dijkstras algorithm takes a relatively lesser time than Floyds and Binary integer programming in finding shortest route. However, Dijkstras algorithm is the better option for identifying the shortest path in larger networks such as railway, water, power distribution and gas pipeline networks.

Fig.2.4: Comparison of computational time of various algorithms

Acknowledgement: The support from Dr.A.M. Ramesh, Senior Scientific Officer from Karnataka Science and Technology Academy is gratefully acknowledged.

References:

1. Dijkstra, E. W., 1959. A note on two problems in connection with graphs. Numerische Mathematik 1: p269-271

2. G.B. Dantzig., 1963. Linear Programming and Extensions, Princeton University Press, Princeton, NJ. p1-625

3. Kambo N.S., 1984. Mathematical Programming Technioques, East-West Press, p124-131

4. Ralph P. Grimaldi., 2003. Discrete and Combinatorial Mathematics- An Applied Introduction, Pearson fifth Edition. Wesley, p591-625

5. Sohana, J, and Sajid,H,Md. 2011. A Comparitive Study on Algorithms for Shortest-Route Problem and some Extensions. International Journal of Basic and Applied Sciences. Vol.11, No. 6. p167-177

6. Vanderbei Robert J., 2008. Linear Programming Foundations and Extensions, Springer, p55-68

Dr. K.M. Roopa, Professor, Dept. of Mathematics, Bangalore Institute of Technology, Bangalore-560004. Mis. H. R. Apoorva, Software Developer, Amazon India, Bangalore

Mr. V.K. Srinivasu, Scientific Officer, KSTA, Dept. of Science and Technology, GoK, Bangalore.

Mr. M.C.Viswanath, Assistant Professor, Dept. of Mathematics, Nagarjuna college of Engineering and Technology, Bangalore.