Case Study of Shortest Path Algorithms and Implementation using MATLAB

Reader Impact Factor Score
[Total: 9 Average: 5]

Published on International Journal of Biology, Physics & Mathematics
Publication Date: July 25, 2019

Yee Yee Htun
Ph.D (Applied Maths), Department of Engineering Mathematics
TU (Hmawbi), Hmawbi Township, Yangon Division, Myanmar

Journal Full Text PDF: Case Study of Shortest Path Algorithms and Implementation using MATLAB.

Abstract
Shortest path problems are among the most studied network flow optimization problems withinteresting application across a range of fields. In this paper, three shortest path algorithms arediscussed via Dijkstra’s Algorithm (one to all pairs of nodes), Floyd Warshall’s Algorithm (all to allpairs of nodes) and Linear Programming Problems (LPP). These algorithms are also solved usingMatlab software, which gives quick results for larger nodes. By this research, we can sucessfully study how many ways to find shortest path. Graph technique in Matlab can also be applied to be simply solved the shortest path problems. The application of Direct Graph and Undirect Graph of shortest path was implemented for the route of ferry bus, North Dagon township to TU (Hmawbi).

Keywords: Shortest path, Dijkstra’s Algorithm,Floyd Warshall’s Algorithm, Linear Programming Problems, Matlab software & Direct Graph.

1. INTRODUCTION
Finding the shortest path is an important task in network and transportation related analysis. Shortestdistance problems are inevitable in road network applications, such as city emergency handling anddriving system, where optimal routing has to be found. Therefore, network optimization has alwaysbeen 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 solutionhas to be found quickly. Hence, efficiency of an algorithm is very important to determine the shortestroutes are between nodes in a network.
There are many algorithms that can be used to determine the shortest route between two nodes in anetwork. In this paper, two standard algorithms Dijkstra’s algorithm and Floyd Warshall’salgorithm 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 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 routedetermined using Complementary Slackness Theorem.(Dr. Roopa, K.M., 2013).

2.GRAPH IN MATLAB
A directed graphwith four nodesand three edges is as shown in Picture 1 in Matlab. Graph theory functions in the toolbox apply basic graph theory algorithms to sparse matrices. A sparse matrix represents a graph, any nonzero entries in the matrix represent the edges of the graph, and the values of these entries represent the associated weight (cost, distance, length, or capacity) of the edge. Graph algorithms that use the weight information will cancel the edge if a NaN or an Inf is found. Graph algorithms that do not use the weight information will consider the edge if a NaN or anInf is found, because these algorithms look only at the connectivity described by the sparse matrix and not at the values stored in the sparse matrix.(matlabexpo.co.kr, 2016).

Picture 1. Direct Graph example

Sparse matrices can represent four types of graphs:
1) Directed Graph — Sparse matrix, either double real or logical. Row (column) index indicates the source (target) of the edge. Self-loops (values in the diagonal) are allowed, although most of the algorithms ignore these values.
2) Undirected Graph — Lower triangle of a sparse matrix, either double real or logical. An algorithm expecting an undirected graph ignores values stored in the upper triangle of the sparse matrix and values in the diagonal.
3) Direct Acyclic Graph (DAG) — Sparse matrix, double real or logical, with zero values in the diagonal. While a zero-valued diagonal is a requirement of a DAG, it does not guarantee a DAG. An algorithm expecting a DAG will not test for cycles because this will add unwanted complexity.
4) Spanning Tree — Undirected graph with no cycles and with one connected component.There are no attributes attached to the graphs; sparse matrices representing all four types of graphs can be passed to any graph algorithm. All functions will return an error on nonsquare sparse matrices.

2.1 Finding the Shortest Path in a Directed Graph
1) Create and view a directed graph with 6 nodes and 11 edges.
2) Biograph object with 6 nodes and 11 edges.
3) Find the shortest path in the graph from node 1 to node 6.
4) Mark the nodes and edges of the shortest path by coloring them red and increasing the line width.
This example Graph results can be shown as in Picture 2 (a).

2.2 Finding the Shortest Path in an Undirected Graph
1) Create and view an undirected graph with 6 nodes and 11 edges.
2) Biograph object with 6 nodes and 11 edges.
3) Find the shortest path in the graph from node 1 to node 6.
4) Mark the nodes and edges of the shortest path by coloring them red and increasing the line width.
This example Graph results can be shown as in Picture 2(b).
(a) (b)
Picture 2. Direct Graph and Undirect Graph in Matlab for 6 nodes(www.mathwork.com)

3. SHORTEST PATH ALGORITHMS
3.1 Dijkstra’s Algorithm
Dijkstra’s algorithm considers two sets:
i) set P, which at any specific point consists of all the nodesthat were encountered by the algorithm;
ii) set S, a precedence set, which at any specific pointconsists of the precedent node for each node in the network. Apart from these sets, the algorithmutilizes the following distance information.
qij, for i, j=1, 2, 3, 4…n and i≠j, denote the weight of the directed edge (arc) from vertex i to vertex j.
If there is no arc from i to j, then qij, is set to be infinity.tj, for j=1, 2, 3, 4…n and j≠s where s is the start index. Also,
tj = q1j for j=2,3,4…n (1)
In each iteration, the sets P and S as well as the set of all tj, for j=1, 2, 3, 4…n and j≠s, that are outputfrom 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 tj 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, 4…n 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 Dijkstra’s algorithm aregiven 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.
Picture3 shows an example of using Dijkstra’s Algorithm.

Picture 3. Example of Dijkstra’s Algorithm

3.2Floyd Warshall’s Algorithm:
Floyd Warshall’s Algorithm is a graph analysis algorithm to find the shortest route between any twonodes in a network with positive or negative edge weights with no negative cycle. This algorithm usesthe dynamic programming technique to solve the shortest path problem between all pairs of nodes (allto all) in a directed network. It represents the network as a square matrix with n-rows and n- columnsand 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 (i,j)= ∞.
The steps to trace the shortest path between two nodes, say i and j using Floyd-Warshall’s
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.

Picture 4. Shortest Route Network
To determine the shortest distance and shortest paths between all pairs of nodes in atransportation network as shown in Picture 4, using Iteration (3): Set k=3. Consider third column and third row of D3 as pivot column and pivot rowrespectively. Except d (1, 3), all the entries in the pivot column are infinity and also except d (3, 5) andd (3, 7), all the entries in the pivot row are infinity. Further, apply transitivity property to obtain thefollowing 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 D3and S3.
Continuing in this way, the final matrix in the last iteration where none of the entries in the d (i,j) canbe 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 as shown in Picture 5.

Picture 5. Iteration 7 Results ( Dr. Roopa, K.M., 2013).

3.3 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 throughalgebraic method, by introducing slack variables which gives better result compared to any othersoftware packages. By using the first and final tableaus of algebraic method , the dual problem can also be solved using Matlab software. For example, if the solutions obtained from Matlab software aregiven 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 thatsatisfy the above constraints the following routes: 1-3, 3-4, 3-5, 4-7, 5-7, 5-6 and 6 -7 are obtained. Fromthese sequence of routes 1-3, 3-4, 4-7, the shortest route 1—3—4—7, which is of distance 22 units fromnode 1 to node 7 is traced. Similarly, other alternate shortest routes that can be obtained are: 1—3—5—7and 1—3—5—6—7 respectively.
The shortest route can also be determined using Complementary Slackness Theorem . 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, fromthe 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;x56–x67 =0; x47+x57 +x67 =1 (3)
By solving above system of linear equations using Gauss Elimination Method, the system in echelon formbecomes:
x34+ x35 = 1; x35+ x47 =1; x47+x56 + x57 =1; x47+x57 +x67 =1 (4)
In the above system of equations, there are 4 equations (r=4) with 6 unknowns (n=6) and two freevariables (x35, x56,). Hence, the possible choices are: (0,0),(0,1),(1,0),(1,1). Each of these possible choicesmay or may not be the solution points because the dependent variables have the restriction, xij = 0 or 1.( Dr. Roopa, K.M., 2013).

4.IMPLEMENTATION OF SHORTEST PATH
(BETWEEN NORTH DAGON-MAWATA BUS STOP AND TU (HMAWBI))
The case was assigned as to find shortest path between Mawata Bus Stop of North Dagon township and TU(Hmawbi). By solving this case, the author can apply low cost and minimum time to arrive TU(Hmawbi) from her home. There are 9 main Bus Stations as focal points. But there are a lot of Bus Stops Between each focal Bus Stations. Unit are per miles to be considered. The m-script of this case is shown in Picture 6.

Table-1 Nodes Assignment
No. BUS STOPS NODE
1 Ma wa ta 1
2 Bay lie 2
3 Aung migalar highway station 3
4 8 miles 4
5 Saw bwar gyi kyone 5
6 Htaut kyant 6
7 Toll gate 7
8 Hmawbi market 8
9 TU Hmawbi 9

Picture 6. M-script of Implementation Case

5. RESULTS
As a result of implementing shortest path in Matlab, author can make effort of cost and time to go to office from home everyday. The Resut is to use Bus No (99) between Mawata Bus stop to Sawbwargyi Goan Bus stop, and again to TU(Hmawbi) with Bus No (37). The minimun cost for a route is 700 MMK. The results from Matlab program are shown in Picture 7 (a) and (b).

(a) Direct Graph (b) Undirect Graph
Picture 7. Implementation Results

6. CONCLUSION AND RECOMMENDATION
This paper has presented the results of implementing or application of shortest path algorithms in real case. Effectiness of Matlab software can also be proved in this paper. All three algorithms of shortest path finding methods are studied and compared. It is evident that Dijkstra’s algorithm takes a relatively lesser time than Floydsand Binary integer programming in finding shortest route. However, Dijkstra’s algorithm is the betteroption for identifying the shortest path in larger networks such as railway, water, power distribution andgas pipeline networks. For simplicity, the author mainly applied Direct Graph methods that used Dijkstra’s algorithm in background of Matlab. This research paper carried out mainly case study of three shortest path finding concepts and analysis with real world application.

7. REFERENCES
1. Dr. Roopa, K.M., Apoorva, H.R1., Srinivasu,V.K.2 and Viswanatah, M.C 3,“A Study on Different Algorithms for Shortest Route Problem”, International Journal of Engineering Research & Technology (IJERT) ,Vol. 2 Issue 9, September,2013.
2. Algorithms in Java, Chapter 21,http://www.cs.princeton.edu/introalgsds/55dijkstra.
3. Floyd, Robert W. (June 1962). “Algorithm 97: Shortest Path”. Communications of the ACM 5 (6): 345. doi:10.1145/367766.368168 (http:/ / dx. doi. org/ 10. 1145/ 367766. 368168).
4. http://www.matlabexpo.co.kr, 2016.
5. http://research.microsoft.com/users/goldberg.
6. http://www.mathwork.com