Dijkstra Algorithm Optimization
Truong-Giang Ngo1*, Thi-Kien Dao2, Jothiswaran Thandapani2,3, Trong-The Nguyen,4, Duc-Tinh Pham5,6, Van-Dinh Vu7
1Faculty of Computer Science and Engineering, Thuyloi University, Hanoi, Vietnam;
2Fujian Provincial Key Laboratory of Big Data Mining and Applications, Fujian University of Technology, Fuzhou, China;
3Anna University, Chennai, India;
4Haiphong University of Management and Technology, Haiphong, Vietnam;
5Center of Information Technology, Hanoi University of Industry, Hanoi, Vietnam;
6Graduate University of Science and Technology, Vietnam Academy of Science and Technology, Vietnam;
7Faculty of Information Technology, Electric Power University, Hanoi, Vietnam
giangnt@tlu.edu.vn,jvnkien@gmail, jothiswaran14@gmail.com jvnthe@gmail.com, tinhpd@haui.edu.vn,dinhvv@epu.edu.vn
Abstract. The transportation cost, running vehicle time, duration, and distance cost, the route network of revealed urban vehicles, are considered to need to be analyzed meaningfully and reasonably planned. This paper suggests an analysis of urban traffic vehicle routing based on the Dijkstra algorithm optimization that is as a solution to the road selection and optimization under various constraints jointly built in the central metropolitan area. The leading metropolitan area road network's various constraints are to consider the road condition factors and the risk resistance in road planning. The analysis and realization are verified with the geocoding, network topology, and network analysis. The results show that the integration of network analysis technology and the Dijkstra algorithm realizes the urban vehicle route's optimization decision. Still, the improved Dijkstra algo- rithm reduces the number of node visiting and time complexity. Under the driving time and distance constraints, the speed limit, road hierarchy, and road condition are the line selection's restrictive factors. The graphical description could provide technical support and reference for the driver's driving strip and traffic manage- ment department for decision making.
Keywords: Urban traffic; Dijkstra algorithm; Constraint conditions; Path anal- ysis
1 Introduction
Path observation is one of the research materials of an overview of urban traffic net- works[1] and a part of the spatial analysis method's spatial analysis method[2]. It is
commonly used in urban road maintenance, network coordination[3], traffic planning, and others[4]. The center of route analysis is the shortest path and the safest path, and the path optimization is to use the concept of tactical research planning to maximize the organizational efficiency and usage and road network, vehicle routing, delivery of goods, etc.,[5].
In the case of confidence, there have been several studies on the shortest path anal- ysis algorithm, e.g., Bellman algorithm[6], Dijkstra algorithm[7], and Dreyfus algo- rithm[8] have been the traditional algorithms. Nonetheless, under complexity, the short- est path problem can be loosely separated into four parts. This paper looks at the most straightforward path of random road length change, the shortest route with different cost functions, the shortest path with random road length change under the condition of time independence, and the shortest path of interval length.
Nevertheless, in the actual driving of urban vehicles, the above shortest path studies do not consider unknown considerations of the other road route conditions, e.g., rush hours, limited speed, or road situation [9]. Therefore, this study does more work fo- cused on optimization allocation based on the Dijkstra algorithm. First, the urban road network is transformed into a driven graph, including nodes and connections, using the geographic information network mapping technology. The municipal road is trans- formed into a directed graph. Second, we consider several factors. e.g., the type of route, node stay time, speed limit, the direction of driving of vehicles, and other factors. A starting point to the endpoint is measured and evaluated with the time and cost to opti- mize global results. It means the time or expense from the starting point to the parameter is calculated according to the time cost and distance.
Besides the expense restriction considerations and the calculated optimum paths, the shortest route scenarios under unconstrained conditions [10], hazard road condition, and speed limit mode are also considered for testing on the spot.
2 Related Work
2.1 Dijkstra Algorithm
Dijkstra algorithm is a standard algorithm for finding the shortest path in graph theory proposed by Dijkstra, a Dutch computer scientist, in 1959[13]. The algorithm can find the shortest path from a point in a graph to any other vertex. Dijkstra algorithm divides network nodes into three parts: unlabeled in the network graph, and all nodes are ini- tialized as unlabeled nodes. In the process of searching, the nodes that are connected in any path and travel nodes are temporarily marked nodes. In each cycle, the shortest path length from the origin point is searched from the temporarily marked nodes as the per- manently marked nodes until the nodes are found, As shown in Figure 1, assuming that the origin point of the node network is node 0 and the target point is node 4, the shortest path distance between node 0 and node 4 is calculated (the length between nodes is assumed).
Fig. 1. The meshed network of the route
Suppose each node has a pair of labels(𝑤𝑖, 𝑝𝑗), 𝑤𝑖 is the length of the shortest path from the origin point to the target point, 𝑤𝑗 is the shortest path length from the origin point s to any node j (the shortest path from the vertex to itself is the zero path (the path without arc), and its length is equal to zero), and 𝑝𝑗 is the length from the origin point s to the node j The shortest path from the origin point I to the target node j is solved. The basic process is as follows:
1) Initialization. The origin point is set to
① If the shortest path length 𝑤𝑠= 0, 𝑝𝑠 is null;
② The path length of all other nodes is 𝑤𝑖= ∞, 𝑝𝑖= 𝑠;
③ Mark the origin point S. mark all marked nodes 𝑘 = 𝑠, and set other nodes as unmarked
2) Verify the distance from all marked nodes K to their directly connected unlabeled nodes J, and set
𝑤𝑗 = 𝑚𝑖𝑛{𝑤𝑗, 𝑤𝑘+ 𝑑𝑘𝑗} (1) where 𝑤𝑗 is the shortest path length of unlabeled node j, 𝑤𝑘 is the shortest path length of labeled node k, and 𝑑𝑘𝑗 is the direct connection distance from node k to node j.
3) Select the next point. From all unlabeled nodes 𝑤𝑗, select the smallest labeled node i, that is, 𝑤𝑖= min𝑤𝑗 (all unlabeled nodes j), and node i is selected as the point in the shortest path and set as the marked point
4) Find the previous point of node I. find the point j′directly connected to node i from the marked node. As the previous point, set i = j′
5) If all nodes have been marked, the algorithm will find the shortest path; otherwise, mark 𝑘 = 𝑖 and go to step (2). Table 1 shows a list of an example of the shortest path of node 0 to node 4 processing.
Table 1. List of an example of the shortest path of node 0 to node 4 processing.
cycle Node set s
Number of marked nodes K
Distance d between node 0 and
1 D{0}
Distance d between node 0 and
1 D{1}
Distance d between node 0 and
2 D{2}
Distance d between node 0 and
3 D{3}
Distance d between node 0 and
4 D{4}
initialization {0} - 0 10 ∞ 30 100
1 {0,1} 1 0 10 60 30 100
2 {0,1,3} 3 0 10 50 30 90
3 {0,1,3,2} 2 0 10 50 30 60
4 {0,1,3,2,4} 4 0 10 50 30 60
2.2 Algorithm Optimization
The optimization is implemented based on the Dijkstra algorithm as follows: firstly, the temporary set NB𝑠 of the starting point, the neighbor nodes 𝑘 with the smallest distance is selected as the transition point, and at the same time, it is assigned to the identification set S. The union of the temporary set of all nodes in the identification set s and the difference set of the identification set (∪ NB𝑠 𝑆, i ∈ S), a node 𝑊𝑘 with the minimum path distance value is selected as the next transition point and is assigned to the identi- fication set S. Repeat the above process until all nodes are identified |𝑠| = 𝑛, and the algorithm ends. Let NB𝑖 be the temporary set of nodes i, S be the identification set, 𝑤𝑖 be the shortest path length from source point s to node j, 𝑃𝑖 be the previous node of j point in the shortest path from s to j, and 𝐷𝑖𝑗 is the distance from node i to node j.
(1) Initialize identity collection S = {s}，𝑤𝑖= 𝑑𝑠𝑖(i ∈ NB𝑠) otherwise 𝑤𝑖= ∞(i ∈ NB𝑠)；𝑃𝑖= s.
(2) If the distance between 𝑘 temporary set node and origin point is the smallest 𝑑𝑠𝑘 = 𝑚𝑖𝑛𝑑𝑠𝑖, then S = S ∪ {k}, j ∈ NB𝑠
(3) Modify the 𝑤𝑖 value in k temporary set node NB𝑘= 𝑆, 𝑤𝑖= min {𝑤𝑖+ 𝑑𝑘𝑖} ; if 𝑤𝑖 value changes, then 𝑃𝑗= 𝑘, 𝑗 ∈ NB𝑠− 𝑆
(4) Select the minimum value of 𝑤𝑖 in the marked temporary node, set a and classify it into s, 𝑤𝑘= min𝑤𝑖, S = S ∪ {k} if |𝑠| = n, the node has been identified, and then the algorithm is terminated; otherwise, go to step (3).
For the network graph with n nodes, the Dijkstra algorithm needs a total of 𝑛 − 1 iter- ations to solve the shortest path, and a new node is added to the temporary node-set in each iteration. Because the number of nodes not in the temporary node-set is 𝑛 − 𝑖 in the i-th iteration, then 𝑛 − 𝑖 is needed in the i-th iteration. The number of nodes pro- cessed is
∑(𝑛 − 𝑖)
𝑛−1
𝑖=1
=𝑛(𝑛 − 1)
2 (2)
When the number of network nodes in equation (2) is n, the time complexity of the path solution is O(𝑛2), which is the time complexity of the shortest path from the origin point to the other nodes in the network graph. With the increase of the total number of nodes n, the calculation efficiency, and storage efficiency decrease.
The time complexity O(𝑛2) depends on the number of elements in the temporary set NB𝑠 of the transition point k, then the space complexity of the optimization algorithm is O (n × P), where p is the space occupied by the node object under the adjacency matrix storage structure 𝑁 × 𝑁, which is a constant According to the number of points and road sections, the average out degree e of nodes can be obtained, i.e
e =𝑚
𝑛 (3)
where m is the number of road sections.
Generally, in the geographic information system network diagram, e ∈ [1,4], because step 3) and step 4) are search and 𝑉𝑖(i = 1, 2, 3,…,n) The time complexity of step 4 is O (m), i.e. O(n × e).
3 Model Construction
Assumed the road network of a center city by generated randomly is used to facilitate to experiment. The vector elements of options are imported into the local geographic database, e.g., the expressway, national road, provincial road, county road. The topo- logical grade is specified as vector elements of the participating road network. The tol- erance limit value, such as the speed limit and traffic restriction and turning model, is set up, and the road arc segment node is established. The cost and constraint variables are set according to the connection rule between the road network node and arc seg- ment. The cost variable is path cost expense, and the attribute field of the constraint variable is a Boolean value, namely a single line or double line, respectively.
{
𝑅𝑤= (𝑁, 𝑅, 𝐿𝑅)
𝑅 = {(𝑥, 𝑦)|𝑥, 𝑦 ∈ 𝑁, 𝑎𝑛𝑑 𝐿(𝑥, 𝑦)}
𝐿𝑅= {𝑙𝑥𝑦|(𝑥, 𝑦) ∈ 𝑅}
(4) where 𝑅𝑤 represents the road network; 𝑁 represents the node-set; 𝑅 represents the set of road sections, whose elements are ordered pair (𝑥, 𝑦), and indicates that there is a directed path from node x to node y; 𝐿𝑅 represents the weighted length of the section, and its elements 𝐿(𝑥, 𝑦) denote the weighted length of the directed section (𝑥, 𝑦); 𝑙𝑥𝑦 is the length of any section from node x to node y.
The weighted length 𝐿𝑅 of a road segment refers to the optimal path which is solved by integrating various dynamic and static attribute constraints according to the multi-ob- jective function and planning requirements, rather than the actual distance or length of the path. Therefore, the optimal path not only refers to the shortest distance in the gen- eral geospatial sense. It can also be extended to time, cost, line capacity.
Some constraints are also considered when nodes or sections in the network cannot operate due to some emergencies, such as traffic accidents, or the original optical path needs to be modified. For example, the road is under maintenance, the distance of the optimal path changes, and maintenance status. If there is a traffic accident at the inter- section, it is temporarily not passable; that is, the nodes in the network can not run, thus prolonging vehicles' travel time.
The comprehensive road resistance C of any path is calculated by the weighted sum- mation method
C = ∑ 𝐶𝑖= ∑(𝐷𝑖1𝑎1+ 𝐷𝑖2𝑎2+ ⋯ + 𝐷𝑖𝑗𝑎𝑗)
𝑛
𝑖=1 𝑛
𝑖=1
(5) where 𝐶𝑖 is the comprehensive road resistance of section i, 𝐷𝑖𝑗 is the score of the road resistance factor, and 𝑎𝑗 is the weight of j road resistance factor. A parameter is used to adjust the weight according to the situation of environmental conditions.
𝑎𝑗𝑡= 𝜇 × 𝑎𝑗𝑡−1 (6) where 𝜇 is an adjusting variable based on the scenario of environmental conditions.
The upper limit measure is used to calculate the 𝐷𝑖𝑗 a score of any road section and the calculation formula is
𝐷𝑖𝑗= 𝑑𝑖𝑗/𝑑𝑗,𝑚𝑎𝑥 (7)
where: 𝐷𝑖𝑗 is the score of 𝑗 road resistance factor of section 𝑖; 𝑑𝑖𝑗 is the actual value of road resistance factor; 𝑑𝑗,𝑚𝑎𝑥 is the maximum actual value of J road resistance factor.
Algorithm 1. The adjusted optimal path based on the Dijkstra algorithm Input: A bi-directed Graph with weights 𝐷𝑖𝑗 = (𝑁𝑖𝑗; 𝐶𝑖𝑗), the set of all nodes 𝑁, the set of weighted edges of connected nodes 𝐶. The source and target node 𝑛𝑠
and 𝑛
𝑡, respectively.
Output: Shortest path and the length from the source node 𝑛𝑠
to the target node 𝑛
𝑡.
1: Initialization.
Visited nodes 𝑁
𝑒 = 𝑛𝑠. 𝑑(𝑛𝑠) = 0, where 𝑑(𝑛𝑡𝑖) is the minimum cost of theshortest path from n
sto 𝑛
𝑡𝑖. 𝑁
𝑢 = 𝑁 − 𝑁𝑒, where N
uis the set of nodes to n
swith the undetermined shortest path. 𝑑(𝑛
𝑡𝑖) = 𝑚𝑖𝑛(𝐶(𝑛𝑠; 𝑛𝑡𝑖)), if 𝑛𝑡𝑖is a suc- cessor to 𝑛
𝑠, or else, 𝑑(𝑛
𝑡𝑖) = 1, where 𝐶(𝑖; 𝑗) is the cost between node i andnode 𝑗 as Eq.(5)
2: Repeat the following steps until there are no nodes in the set 𝑁
𝑢. 2.1 Put the node in N
uthat have the minimum cost to the old n
sas the new source n
s. Move the new source node n
sto 𝑁
𝑒;
adjust the weight according to the situation of environmental conditions as Eq.(6).2.2 Set 𝑑(𝑛
𝑡𝑖) = 𝑑(𝑛𝑠) + 𝑚𝑖𝑛(𝐶(𝑛𝑠; 𝑛𝑡𝑖)).3: Find the shortest path from the source node n
sto the target node n
t. 4: return d(n
t), N
e.
The initial work of the Dijkstra algorithm is only dealing with the shortest path between two points. Mathematically, these points must be represented by nodes in the graph network. Bellman Ford implemented the possibility of fixing
4 Results and Discussion
In order to test the performance of the proposed scheme, some lines assuming roads are generated randomly in a specified metro urban area based on the grid and sample points under constrains of the condition roads and obstacles. Table 2 lists the comparison of theoretical and actual driving time of the optimized route. It is seen that the travel time of the optimized route, the real travel time is longer, the difference between the mini- mum and maximum travel time is 1.2min and 2.9min, respectively. In the obstacle mode, the driving time of line 4 is 1.0 min longer than that of line 3. The driving time of line 4 is 1.0 min longer than that of line 3. In the speed limit mode, the actual driving time of urban vehicles inline 5 is limited by road congestion, traffic capacity, and traffic
information, which is 1.2 min longer than the real driving time on line 6 is 2.3 min longer than the theoretical driving time of line 6. In the case of a 30 s delay at the intersection node, the actual driving distance is more reasonable, and the real driving time is longer. Therefore, the node delay, road conditions, and speed limit are the main factors affecting the urban vehicle route selection. The number of nodes in the optimal path plays a leading role in the driving time and distance.
Table 2. The obtained results of the optimization of the Dijkstra algorithm for actual driving time and vehicle routing.
Serial
number Line selection condi-
tions Distance / m
Theoreti- cal driving time / min
Actual driving time / min
Travel time dif- ference /
min
Num- ber of nodes
Line 1 The shortest distance in unlimited road class and speed mode
4377.8 10.7 11.9 1.2 19
Line 2 Minimum time in un- limited road class and
speed mode 4385.2 9.7 11.5 1.8 17
Line 3 Shortest distance in
obstacle mode 4610.3 10.7 12.1 1.4 20
Line 4 Shortest time in obsta-
cle mode 4630.6 10.2 13.1 2.9 18
Line 5
The shortest distance under speed limit
mode 4455.2 10.9 13.2 2.3 17
Line 6 The shortest time un-
der speed limit mode 4739.3 10.5 12.0 1.5 21 Line 7 The delay time of 30s
at the node is the short- est
4463.3 15.9 18.4 2.5 17
Fig. 2a displays the setting for generating points in the road network. Fig. 2b shows the generated obstacle maps and the roads' points as road network grade and speed limit mode, randomly prioritizing provincial roads, national highways, and urban trunk roads, and then choosing urban secondary trunk roads and township roads. Fig. 2c dis- plays the proposed method's optimal paths close to the actual travel time and distance cost. Drivers would be advised as a priority to these kinds of conditions as assuming that the speed limit of trunk roads is 30km / h, and of crowed streets is 35km / h, In the speed limit mode, the shortest path needs to drive 4455.3m, and the travel time cost is 13.2min.
a) The generated points in the roads network b) The generated obstacle maps in the roads as road network
c) The optimal paths of the proposed method close to the actual travel time and distance cost
d) The shortest path obtained by the Dijkstra be- tween Hoabinh park and the Linhnam-Hoang Mai, Hanoi, as an example of the shortest under the con-
dition of daily road status
Fig. 2. The proposed scheme's optical paths based on the Dijkstra for analysis of urban traffic vehicle routing in terms of the travel time and distance cost
Fig. 2d shows the shortest distance between Hoabinh park and the Linhnam-Hoang Mai, Hanoi, as an example of the most straightforward under the condition of daily road status and vehicle speed in the middle afternoon. Assuming that Hoabinh the park, Ha- noi is the initial source point and the Linhnam–Hoangmai, Hanoi as the target node, the optimal distance, and time path between Hoabinh-Park and the Linhnam-Hoangmai can be calculated at any intersection. The route length is 19377.8m, and the time cost is 25.7min, while the route distance under time constraint mode is 19374.9m, and the minimum driving time is 24.7min. In actual driving, route selection is affected by driv- ers' preference for the shortest time and shortest distance. Fig.3 shows a comparison of the suggested approach's outcomes regarding the average optimization error rate with the A* algorithm and Dynamic programming schemes to analyze Urban traffic vehicle paths. It can be seen that the suggested approach based on Dijkstra algorithm optimiza- tion produces the lowest average converge error rate in comparison with other methods.
Fig.3. A comparison of the suggested approach's outcomes regarding the average optimization error rate with the A* algorithm and Dynamic programming schemes to analyze Urban traffic
vehicle paths
Table 3. The comparison of the results of the proposed scheme with the A-star algorithm and Dynamic programming methods.
Approach The obtained best cost
The averaged the optimal cost
The exe- cuted time
A* algorithm[11] 19378 20263 2670
Dynamic program-
ming algorithm[12] 19375 20623 2580
Proposed scheme 19368 20233 2376
Table 3 illustrates the comparison of the proposed scheme's results with the A-star al- gorithm and Dynamic programming methods. It is seen that the proposed approach produces the results efficiently for the analysis of urban traffic vehicle routing planning.
5 Conclusion
This study proposed an analysis of urban traffic vehicle routing based on the Dijkstra algorithm optimization for suggesting road selection and optimization under various constraints jointly built in the central metropolitan area. The optimal path cost depends on the number of path nodes, link constraints, and speed limit conditions. In this planned scheme of the road network, the specified for both origin point and the target point, the Dijkstra's obtained optimal path was implemented under distance and time cost constraints. The analysis and realization are verified with the geocoding, network topology, and network analysis tools. The results show that the integration of network analysis technology and the Dijkstra algorithm realizes the urban vehicle route's opti- mization decision. Also, the Dijkstra algorithm reduced the number of node visiting and time complexity. Under the driving time and distance constraints, the speed limit, road hierarchy, and road conditions are the line selection's restrictive factors. The
graphical description could provide technical support and reference for the driver's driv- ing strip and traffic management department for decision making.
References
1. Dao, T., Nguyen, T., Pan, J., Qiao, Y., Lai, Q.: Identification Failure Data for Cluster Heads Aggregation in WSN Based on Improving Classification of SVM. IEEE Access. 8, 61070–
61084 (2020). https://doi.org/10.1109/ACCESS.2020.2983219.
2. Stucky, J. dan: On applying viewshed analysis for determining least-cost paths on digital elevation models. Int. J. Geogr. Inf. Sci. 12, 891–905 (1998).
3. Dao, T., Yu, J., Nguyen, T., Ngo, T.: A Hybrid Improved MVO and FNN for Identifying Collected Data Failure in Cluster Heads in WSN. IEEE Access. 8, 124311–124322 (2020).
https://doi.org/10.1109/ACCESS.2020.3005247.
4. Bang, S., Heo, J., Han, S., Sohn, H.-G.: Infiltration route analysis using thermal observation devices (TOD) and optimization techniques in a GIS environment. Sensors. 10, 342–360 (2010).
5. Magzhan, K., Jani, H.M.: A review and evaluations of shortest path algorithms. Int. J. Sci.
Technol. Res. 2, 99–104 (2013).
6. Awerbuch, B., Bar-Noy, A., Gopal, M.: Approximate distributed bellman-ford algorithms.
IEEE Trans. Commun. 42, 2515–2517 (1994).
7. Jianya, Y.Y.G.: An efficient implementation of shortest path algorithm based on dijkstra algorithm. J. Wuhan Tech. Univ. Surv. Mapp. 3, (1999).
8. Fuchs, B., Kern, W., Wang, X.: Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees. Math. methods Oper. Res. 66, 117–125 (2007).
9. Nguyen, T.-T., Qiao, Y., Pan, J.-S., Chu, S.-C., Chang, K.-C., Xue, X., Dao, T.-K.: A hybridized parallel bats algorithm for combinatorial problem of traveling salesman. J. Intell.
Fuzzy Syst. 38, 5811–5820 (2020). https://doi.org/10.3233/jifs-179668.
10. Nguyen, T.-T., Dao, T.-K., Kao, H.-Y., Horng, M.-F., Shieh, C.-S.: Hybrid Particle Swarm Optimization with Artificial Bee Colony optimization for topology control scheme in wireless sensor networks. J. Internet Technol. 18, (2017).
https://doi.org/10.6138/JIT.2017.18.4.20150119.
11. Duchoň, F., Babinec, A., Kajan, M., Beňo, P., Florek, M., Fico, T., Jurišica, L.: Path planning with modified a star algorithm for a mobile robot. Procedia Eng. 96, 59–69 (2014).
12. Psaraftis, H.N., Tsitsiklis, J.N.: Dynamic shortest paths in acyclic networks with Markovian arc costs. Oper. Res. 41, 91–101 (1993).
