**Shortest Path from Bandar Tun Razak to Berjaya Times Square using Dijkstra Algorithm** **Nur Syuhada Muhammat Pazil1\*, Norwaziah Mahmud2, Siti Hafawati Jamaluddin3, Nur Farasyaqirra Binti Mustafa4** 1Faculty of Computer & Mathematical Sciences, Universiti Teknologi MARA Melaka Branch, Malaysia. 2,3,4Faculty of Computer & Mathematical Sciences,Universiti Teknologi MARA Perlis Branch, Malaysia. Corresponding author: \*syuhada467@uitm.edu.my Received Date: \*date Accepted Date: \*date ABSTRACT *The shortest path is an issue that involves the route from one point (nodes) to another. It is to find a path with a minimum travelling time. Nowadays, traffic problems have affected many transport users especially in Kuala Lumpur area. The time wasted on the road causes a lot of problems to the users. Furthermore, the costs between two destinations are rather expensive. Therefore, the inability of users to use the shortest path has attracted the researcher to propose several travel alternatives to overcome this problem. In addition, this study will help to improve the efficiency of the road and make people want to use it more often. The objectives of this study are to find the shortest path from Bandar Tun Razak to Berjaya Times Square and to cut down the cost between these two destinations. The time of the shortest path problem and the cost problem are drawn separately. Moreover, Dijkstra algorithm is applied to find the shortest path. The shortest path is calculated by using C programming of Dev C++. Nevertheless, both time and cost of shortest path are constructed in different paths. The time and cost of the journey are described by driving a car from Bandar Tun Razak to Lebuhraya SMART to Kampung Pandan, then Berjaya Times Square. The total time taken is 23 minutes (RM8.00), whereas, the cost is based on the shortest path from Bandar Tun Razak to Taman Maluri to Seasons Tower and Berjaya Times Square. The minimum cost is RM4.00 (30 minutes).* *Keywords: shortest path, Dijkstra algorithm, cost, time* **INTRODUCTION** Traffic problem has affected transport users. This is because of the time wasted on the road. Although the number of road and expressway is increasing, traffic problems in Kuala Lumpur area still exist. The shortest path is a problem that involves the route from one point (nodes) to another (Kumari & Geethanjali, 2010). It is to find a path with a minimum travelling time. It is important for every passenger especially workers who need to arrive at their workplace on time. For instance, in order to improve the effectiveness of travelling time, there is a need to provide some rational alternatives that can cut down the time of one’s journey. Furthermore, the shortest path is also used to minimize the cost (Gupta et al., 2016). Dijkstra algorithm has been used in general. It is actually a variant to find the shortest path between two nodes, but is a more common variant which fixes a single node as it is the source of node and finds the shortest path from the sources to all the nodes. Dijkstra algorithm builds the optimal path based on the node that it reaches. However, it cannot handle the negative edges (Rohila et al., 2007). In Malaysia, globalization has turned drivers into a complex system nowadays. Mobility has been an easier transportation whether on land, air or water to get through from one destination to another. Therefore, there are a lot of people who prefer to have their own transport such as cars, motorcycles and vans. This is because, it is much easier compared to taking a public transportation. Unfortunately, if driving their own transport, the drivers need to face traffic jam especially in the Kuala Lumpur area. For example, if one family consists of five members and each of them has his/her own car, then the crowdedness on the road will be obvious. The traffic jam in this area is considered as serious since the drivers have to wait on the road for about an hour at least. Furthermore, the costs between two destinations are rather expensive. Since the cost of living in Malaysia increases in every aspect, then it can be a burden for the drivers and they cannot just neglect it. This is because, if the drivers calculate the cost for only one day it can be considered fine but the problem is for those who work in the area of Kuala Lumpur. This is because they need to face this problem for a long period of time. The total cost for fuel and toll can be half of their salary which is not worthy. The traffic situation and costs sometimes change from time to time. These problems can be rectified through the shortest path by using the Dijkstra algorithm. The main objective of this study is to find the shortest path from Bandar Tun Razak to Berjaya Times Square by using Dijkstra algorithm and to cut down the cost between the two destinations. This research applies Dijkstra algorithm to measure the shortest path in the area of Bandar Tun Razak to Berjaya Times Square. It will concentrate among all roads that start from Bandar Tun Razak to Berjaya Times Square that will give the shortest distance and the lowest cost of journey. It will consider several roads that will be chosen as the best road to meet the objective. Data is collected from Google Map and also by driving a car from Bandar Tun Razak to Berjaya Times Square. In order to determine the shortest path for a road between the two destinations, Dijkstra algorithm will be applied. The shortest path will find the shortest distance between the two destinations and also the lowest cost between Bandar Tun Razak to Berjaya Times Square. It can also improve the efficiency of which road and make people want to use it more often. **RELATED WORKS** 1. ***Dijkstra Algorithm*** The purpose of Dijkstra algorithm is it can be applied directly to find a physical direction. Next, it can also be used in networking or for telecommunication applications. Furthermore, it can solve a variety of shortest path problems that arise in plants and also robotics, facility layouts and transportation. Kai et al. (2014) did a research about emergency response system based on Dijkstra algorithmn. The researchers intended to investigate how well the emergency response mechanism decreases hazardous events. It is also used to find a minimum time to arrive at a destination during fatal rescue operations. The integration of Geographic Information System (GIS), Asynchronous JavaScript and XML (Ajax) technologies and web services are used to find the best or optimal route. The reserchers also stated that the shortest path will not solve the problem because there are also some factors that affect travelling time. The reserchers used Dijkstra algorithm in order to search the length of the shortest path from sources to sources. Arjun et al. (2015) stated that the shortest path problem is a problem to find the vertices between the sources on the graph. Engineers usually use Dijkstra algorithm in their calculations. This survey has stated an optimization method which mostly enhanced the nodes selection of the shortest path and data structure and organization. In brief, the optimized Dijkstra algorithm which has advanced space complication, time complication and storage combination, decreases the storage space, data redundancy and hugely increases the running rate. Tirastittam and Waiyawuththanapoom (2014) did a case study an Bangkok metropolitan public transport planning system using Dijkstra algorithm. The research was about public transport planning system, using Dijkstra algorithm, focusing on buses, Bangkok Mass Transit System (BTS) and Metropolitan Rapid Transit (MRT) schedules because the citizens lack of information and they are scared to use the subway system mainly because of the time and safety factors. The researchers’ objective was to design a public transportation planning system by using Dijkstra algorithm in Bangkok area to judge the public transportation users’ satisfaction. Moreover, Jaafar et al. (2014) did a research on intelligent guidance parking system using Dijkstra algorithm. The proposed intelligent parking guidance system is a system that gives the closest vacant bay to drivers with necessary direction stated on a ticket so the driver can find the best lot in a short amount of time. The conclusion that the researchers made is the system has been installed to assist parking users. Moreover, Gupta et al. (2016) did a research about applying Dijkstra algorithm in routing process. The researchers proposed that Dijkstra algorithm is one of the best methods that can be used to calculate the shortest path problem compared to other algorithms. The researchers’ target was to search for the shortest path from sources node to destination node. To search for the shortest path, this algorithm uses connection matrix and weight matrix. The researchers also applied the data in computer networking for routing systems and also in Google map. 2. ***Techniques for the Shortest Path*** One of the research by Patel and ChitraBaggar (2014) was a survey of Bellman-Ford algorithm and Dijkstra algorithm to search for the shortest path in Geographic Information System (GIS) application. The researchers wanted to make a comparison between Bellman-Ford method and Dijkstra method and choose the best one. The main problem in transportation management is finding the shortest path and using the act of Geographic Information System (GIS). The conclusion made by the researchers is that Dijkstra algorithm is very quick to use compared to Bellman-Ford algorithm and it also works widely in real time application. Chandak et al. (2016) stated that there are a variety methods available to discover the shortest path. Examples of methods introduced by researchers are A-star algorithm, Hierarchical A-star and Dijkstra algorithm. The Dijkstra algorithm needs a huge memory and a lot of redundant calculations performed which it can or cannot be functional for the current path. In addition, the hierarchy in the map by dividing it into district by decreasing the computation needed and memory needed by the systems. This can be used when the area in the map is considered big enough. It depends on the application to use the hierarchy to search for the shortest path to decrease the load on the system’s memory. **Research Methodology** The shortest path cannot cross all the vertices. It needs to search for the shortest path from vertex sources to all vertices and then calculate the path between the vertices that are attracted to. Due to its simplicity, it only deals with graphs with non-negative edges. It is often advantageous to route all communication on a sparse spanning sub network, typically a spanning tree. Unvisited vertices are consistently on the list. It selects a vertex and allocates the maximum possible cost for each of other vertex. In each of the following steps of Dijkstra algorithm, it attempts to reduce the cost for every vertex. The cost will be the length of the journey, time taken to achieve that vertex from the source vertex or money. The minimization of cost is a multi-step procedure. Figure 1 shows a network in which the arcs are labelled with the distance between two connected nodes. It will search for the shortest route from the origin *o*, to the destination, t, by using Dijkstra algorithm. The number between the nodes and the next nodes is representing the distance. Vertex 0 represents Bandar Tun Razak, vertex *a* represents Lebuhraya SMART, vertex *b* represents Taman Connaught, vertex *c* represents Taman Maluri, vertex *d* represents Chan Sow Lin, vertex *e* represents Seasons Tower, vertex *f* represents Kampung Pandan and vertex *t* represents Berjaya Times Square. ![](169-1-494-1-6-20201102_media/media/image1.png) Figure 1: Network nodes. **Step 1:** Initialize by displaying the origin as solved. It will be labelled as 0 since it is 0 unit from the origin. Next, each unsolved vertex is connected to an identified solved node. **Step 2:** Evaluate the candidate distance. Candidate distance = distance to the solved nodes + length of arc. **Step 3:** The smallest candidate distance is chosen. Repeat the step until it arrives at the destination node. Evaluate the candidate distance of every connecting arc. **RESULT AND DISCUSSION** Figure 2 shows the shortest routes which are: *o* – *a* – *b* – *d* – *t*. This is because if compared with others, it is the only route that is short which is only 13. ![](169-1-494-1-6-20201102_media/media/image2.png) Figure 2: Network nodes (solved). The time and cost for the research have been made by using the C programming. The time and cost for the journey have been done separately. The procedure for the cost is using the same procedure for time network Table 1 : List of activities
No Activity

Time

(minutes)

Cost

(RM)
1 From Bandar Tun Razak to Lebuhraya SMART 12 3
2 From Bandar Tun Razak to Taman Connaught 9 2
3 From Bandar Tun Razak to Taman Maluri 19 2
4 From Lebuhraya SMART to Kampung Pandan 7 4
5 From Taman Connaught to Berjaya Times Square 30 6
6 From Taman Maluri to Chan Sow Lin 13 2
7 From Taman Maluri to Seasons Tower 10 1
8 From Chan Sow Lin to Berjaya Times Square 11 1
9 From Seasons Tower to Berjaya Times Square 1 1
1. ***Result of the Time Dependent*** ![](169-1-494-1-6-20201102_media/media/image3.png) Figure 3: Time dependent graph network. Table 2: Result for the Time | Node | Distance | Path | | ----- | -------- | --------- | | 0 → 1 | 12 | 0 1 | | 0 → 2 | 19 | 0 1 2 | | 0 → 3 | 9 | 0 3 | | 0 → 4 | 19 | 0 4 | | 0 → 5 | 32 | 0 4 5 | | 0 → 6 | 31 | 0 1 2 7 6 | | 0 → 7 | 23 | 0 1 2 7 | The result in figure 3 shows that the path of 0 1 2 7 is the shortest to minimize the time. It means that the path is from Bandar Tun Tazak to Lebuhraya SMART to Kampung Pandan then Berjaya Times Square. The total time to reach at the destination is 23 minutes. 1. ***Result of the Cost Dependent*** ![](169-1-494-1-6-20201102_media/media/image4.png) Figure 4 : Cost dependent graph network. Table 3 : Result for the Cost | Node | Distance | Path | | ----- | -------- | --------- | | 0 → 1 | 3 | 0 1 | | 0 → 2 | 5 | 0 4 6 7 2 | | 0 → 3 | 2 | 0 3 | | 0 → 4 | 2 | 0 4 | | 0 → 5 | 4 | 0 4 5 | | 0 → 6 | 3 | 0 4 6 | | 0 → 7 | 4 | 0 4 6 7 | Figure 4 shows the result of the cost from Bandar Tun Razak to Berjaya Times Square. It shows that the minimum cost is by using 0 4 6 7 path which is denoted from Bandar Tun Razak to Taman Maluri to Seasons Tower and Berjaya Times Square. The total cost to arrive at the destination is RM4.00. This includes toll and petrol. **CONCLUSION AND RECOMMENDATION** Based on the results, it shows that the main objective of this research has been met. The goal for this research is to optimize the path by limiting the maximum detour and cost from Bandar Tun Razak to Berjaya Times Square. The method that has been used is Dijkstra algorithm. Due to the limited time of the study, the cost dependent and time dependent have been treated separately. The shortest duration is 23 minutes. Furthermore, the cheapest cost is only RM4.00. Therefore, the path can be chosen either for the shortest time or the cheapest cost. This research needs to be continued as it can get a better path. Moreover, other researchers can continue this study by using a different method other than Dijkstra algorithm since it may produce a different result. In addition, other researchers can also continue this study by using a different path or a different destination. Furthermore, new researchers can also add a lot of vertex as it can be more efficient to find the shortest way. **REFERENCES** Arjun, Reddy, P., Shama, & Yamuna, M. (2015). Research on the optimization of Dijkstra’s algorithm and its applications. *International Journal of Science, Technology & Management, 04* (01), 304-309. Borissova, D., & Mustakerov, I. (2015). E-learning tool for visualization of shortest paths algorithms. *Trends Journal of Sciences Research, 2*(3), 84-89. Chandak, A., Bodhale, R., & Burad, R. (2016). Optimal shortest path using HAS, a star and Dijkstra algorithm. *Imperial Journal of Interdisciplinary Research (IJIR), 2*(4), 978-980. Gupta, N., Mangla, K., Jha, A. K., & Umar , M. (2016). Applying Dijkstra’s algorithm in routing process. *International Journal of New Technology and Research (IJNTR),2*(5)*,* 122-124. Jaafar, H., Zabidi, M. H., Soh, A.C., Hoong, T. P., Shafie, S., & Ahmad, A. (2014). Intelligent guidance parking system using modified Dijkstra’s algorithm. *Journal of Engineering Science and Technology,* 132-141. Kai, N., Yao-ting, & Yue-peng, M. (2014). Shortest path analysis based on Dijkstra’s algorithm in emergency response system. *TELKOMNIKA Indonesian Journal of Electrical Engineering,* *12*(5), 3476-3482. Kumari, S.M., & Geethanjali, N. (2010). A survey on shortest path routing algorithms for public transport travel. *Global Journal of Computer Science and Technology, 9*(5), 73-76. Patel, V., & ChitraBaggar. (2014). A survey paper of Bellman-Ford algorithm and Dijkstra’s algorithm for finding shortest path. *International Journal of P2P Network Trends and Technology (IJPTT), 5, 1-4.* Tirastittam, P., & Waiyawuththanapoom, P. (2014). Public transport planning system by Dijkstra algorithm: Case study Bangkok metropolitan area. *International Journal of Social, Behavioral, Educational, Economic, Business and Industrial Engineering, 8*(1), 54-59.