Automatization

An Improved Dijkstra’s algorithm application

to multi-core processors

Qiong Wu 1, 2, Guihe Qin1, Hongliang Li2

1 College of Computer Science and Technology, Jilin University, Changchun, 130122,China

2 College of Humanities & Information of Changchun University of Technology, Changchun,
130122,China

Abstract
Dijkstra’s algorithm is a classic algorithm of shortest path, widely used in the field of GIS. In order to improve the
efficiency of computing, the work proposes an improved of parallelize Dijkstra’s algorithm applied to multi-core
environment. Through the program parallel computing on multi-core at the same time, the method greatly improve
the computational efficiency. Through experimental tests, it shows that efficiency of improved of parallelize Dijk-
stra’s algorithm can increase about 50% when it compared with traditional Dijkstra’s algorithm. While multi-core
environment has become the mainstream of the embedded platform development, Improved of parallelize Dijks-
tra’s algorithm has great value.
Keywords: DIJKSTRA’S ALGORITHM; PARALLELIZATION; MULTI-CORE; THE SHORTEST PATH

1. Introduction mal solution of the shortest path, but because of the

The shortest path analysis of the shortest path need to traverse a large number of vertices, so the ef-
planning algorithm is the key of space network analy- ficiency is low, the time complexity is O (n2), where
sis in the GIS (Geographic Information System) [1]. n represents the number of vertices. Because the scale
In recent years, with the development of the vehicle of road network is often large, massive computing
mounted and road construction, the navigation sys- become the bottleneck of the algorithm [2].In recent
tem become one of the popular application of path years some improved Dijkstra’s algorithms were put
planning algorithm. Current path planning algorithm forward in the literature [6-11], in the calculation
is mainly derived from three theoretical branches [3]: method and optimized storage, etc. But in the on-
the first is based on graph theory, the second is based board systems and handheld devices such as embed-
on artificial intelligence theory, and the third is based ded system, the hardware condition of low computing
on the theory of intelligent control. power become the main obstacle of the development
Dijkstra’s algorithm is a classic representative of of the algorithm.
graph theory and proposed by the Dutch scientist Di- In recent years, the development and populariza-
jkstra in 1959. It is a classical algorithm of the short- tion of multi-core technology has brought changes in
est path. The algorithm abstracts the complex geo- two aspects to the software industry: on the one hand,
graphic information for the network graph. The path multiple CPUs greatly improve the computational ef-
for the network graph with weights of edges, vertices ficiency; On the other hand, the change of the hard-
in the graph represents the location, usually used to ware brings new challenges to the software design
calculate the shortest path between two vertices in the idea and design method. Multi-core processor is that
directed graph. Dijkstra’s algorithm can get the opti- two or more than two core was integrated in a single

76 Metallurgical and Mining Industry No. 9 — 2015

 Automatization
chip, and a computer can contain multiple multi-core processing tasks can give full play to the advantages
processors. According to the position and role of the of multi-core. But at present, there are problems in
cores, it divided into homogeneous and heteroge- the work of transform serial task into parallel pro-
neous. The emergence of the multi-core structure has cessing tasks. An improved of parallelize Dijkstra’s
dominated the area of parallel computing [5].There- algorithm was proposed, experiments show that the
fore, Dijkstra’s algorithm limited by a large amount Parallelized algorithm in terms of speed of increase
of calculation has a new development space. even more than the number of CPU advantage.
This article is divided into the following several Dijkstra’s shortest path algorithm is described be-
parts: section 2 introduces the current research quo of low.
the Dijkstra’s algorithm, section 3 proposed the im- Node a is defined as the source node, the starting
proved of parallelized Dijkstra’s algorithm in multi- point of the vertices, L (i, j) is the distance between
core environment, the fourth quarter comparing the nodes i and j, distance of source node a to node v is
improved algorithm and classical algorithm through defined as D (v), it is sum of all the length of the link
the experimental data, section 5 to summarize work along a certain path from node a to node v (plus the
and put forward the direction of next step. weight). Algorithm is divided into two parts: initial-
2. Related Work ization and computing.
Classical Dijkstra’s algorithm has proposed dif- A. Initialization part. C is collection of network
ferent improvements for different work require- nodes. C = {a}.For all node v not in C, the method
ments by many scholars in practice. In [6], ASAP of calculation D (v) as follows: if the node v and the
algorithms have been proposed based on hierarchi- source directly connected, D (v) = L (a, v), otherwise
cal processing. While APSP algorithm is based on D (v) =∞.
matrix multiplication to achieve a fast optimization B. Computation part. Looking for a node w not
in [7].A Double-Sources shortest path algorithm for in C, D (w) is Min. Add w to C, and for node v is
urban road networks is proposed in [8]. This algo-
not in the C, update the original D (v) value, namely:
rithm starts at searching for the shortest path from the
D (v) = Min [D (v), D (w) + L (w, v)]. Repeat looking
source station and destination station respectively and
for the next node, until all the network nodes are in
simultaneously. It can reduce the time-complexity
C. If computing the minimum distance of source a to
based on Dijkstra’s algorithm and the characteristics
node t, when t into the set C, end of the algorithm, the
of the typical urban road network. MIFDA Algorithm
D (t) is the shortest distance between them. Figure 1
was proposed in [9] for solving Intuitionistic Fuzzy
is a network with five nodes, the calculation process
Shortest Path Problem using the Intuitionistic Fuzzy
of shortest distance from source node a to node e as
Hybrid Geometric operator. It achieves tractability
shown in Table 1.
through tolerance for imprecision, uncertainty and
partial truth. In [10], authors presented an efficient
time-dependent route planning algorithm. It is able
to efficiently compute exact shortest paths in time-
dependent continental-sized transportation networks.
Dijkstra’s algorithm was discussed from the view-
point of discrete convex analysis in [11].
The emergence of multi-core platform soon shows
technical advantage. Bring more powerful computing
performance for users; More important, because it can
invoke multiple threads at the same time work togeth-
er. The traditional serial task on multi-core processor
speed will increase greatly, but the ability to parallel Figure 1. The Network With 5 Nodes

Talbe 1. The Calculation Process of Shortest Distance Between Node a and Node e Algorithm
Step Path D(b) D(c) D(d) D(e)
initialization {a} 2.4 3.4 1.5 ∞
1 {a,d} 2.4 3.3 1.5 7.3
2 {a,d,b} 2.4 3.3 1.5 7.3
3 {a,d,b,c} 2.4 3.3 1.5 6.0
4 {a,d,b,c,e} Push-back path: e,c,d,a

No. 9 — 2015 Metallurgical and Mining Industry 77

 Automatization
[Link] Proposed Improved of Parallelize Dijks- variable AC represents a criterion of the number of
tra’s Algorithm threads.
3.1. The Description of Algorithm In the process of the Dijkstra’s algorithm parallel-
This section description the improved of parallel- ization, set for the number of parallel threads is more
ize algorithm, it is shown in figure 2. Initialization important. Sets the number of split parallel threads
algorithm is the first operate step, the second step to N, number of nodes in network for K. Due to par-
is to calculate AC to parallelize the Dijkstra’s algo- allelized programming involves the split of threads,
rithm, after the third back to the shortest path. Here synchronization, merge etc, need to take up a certain

Figure 2. A Improved of Parallelized Dijkstra’s Algorithm

78 Metallurgical and Mining Industry No. 9 — 2015

 Automatization
amount of memory and time, time consumption of re-
alize the parallelization more than time saved by par-
allel computing when the number of node is smaller,
so parallelized algorithm slower than the traditional
serial algorithm. Figure 3 described the comparison
of the traditional algorithm and Parallelize Dijkstra’s
algorithm in the Windows environment with 2cores
4 threads.

Figure 4. Runtime of Diffrent Parameter α

It indicating the number of nodes fewer or cores

more, using the serial algorithm for calculation is
more reasonable When AC≤1. When the maximum
number of threads AC>1, the number of threads al-
located according to [Link] the number of
threads supplied with the number of system thread
Figure 3. Compared of Runtime when number of calculation over the system hard-
ware.
Where N = 4, 200≤K≤2600. It can be seen from
the figure 2, when K > 1300, the superiority of Par- Table 2. Runtime of Improved of Paralized Algorithm
allelized algorithms to show up. However different with Different α
operating system platforms, different CPU and dif- Run Time
ferent network model will have different influence α=0.8 α=0.6 α=0.5 serial parallelized
Node Number
on the calculate speed of algorithm, therefore, here 600 16 16 31 21 63
introduce a criterion of the number of threads variable 800 47 47 47 47 78
AC. When AC>1, Parallelized Dijkstra’s algorithm 1000 62 62 62 63 94
is called; AC≤1, serial algorithm is called. So it is a 1200 110 109 94 98 109
self-adapt algorithm in figure 2. 1400 140 141 156 146 130
3.2. AC Parameters Discussed 1600 188 203 219 213 177
The split of thread requires a certain resource 1800 234 313 328 318 224
consumption, including time and space. AC associ- 2000 297 328 313 443 302
ates with three factors by research: K (Total number 2200 359 390 375 594 359
node), M(number of cores) and frequency of CPU.
When K is small, using serial algorithm, and when K 4. Experimental Study
is big, it is more rational for using of the parallel algo- This section discusses the methodology used in
rithm because of a large amount of calculation. At the experimental design and observes the experimental
same time, the faster cpu is, the stronger computing results.
power is, it can process more calculations in criteria 4.1. Experiment Platform
time. In turn, it only can process less calculations. The algorithm was experimented on Windows and
AC = ( K / 1000 ) / ( M * (1 − α ) )
2
(2) Linux operating [Link] the experiments, the num-
ber of K is from 200 to 9800, the node of edge be-
It shows the relationship between the AC , the tween the initial value generated by the random func-
nodes number K, and cores number M in Eq.2. M is tion in the [-100,100], with a K * K matrix storage,
inversely proportional to AC, and K is proportional,α all zero and negative on behalf of the ∞.The number
as a factor (α [0,1]), α is smaller when the cpu faster, of positive value of M line of the matrix on behalf
while α is greater when cpu speed is slower. The data of node M has number of edges. Records of prior
of runtime show in figure 4 and Table 2. The experi- nodes using of a one-dimensional array (length of K)
ments show it is more reasonable when α= 0.8. At to store. Figure 5 is shown the prior node of the every
this point, the critical value of conversion algorithm node in figure 1. Nodes in the array respectively rep-
is close to serial algorithm's best number of node. resent the prior node of the node on the array.

No. 9 — 2015 Metallurgical and Mining Industry 79

 Automatization

Node a b c d e
Array # a d a c

Figure 5. Storing of Prior Node

4.2. OpenMP Tools

OpenMP is a Shared memory parallel system of
multithreaded programming technology [4].OpenMP
standard was formed in 1997, used to write portable
multithreaded applications. This model provides a
set of platform-independent compiler directive com- Figure 6. Compaired of Runtime of Two algorithm
mands and environment variables, function calls, in-
struction, to direct the compiler explicitly when us- algorithm under the condition of 2 cores 4 threads
ing the application of parallelism and how to do it. and 4 cores 8 threads. It can see from the figure 7,
OpenMP provides a high-level abstract description a serial algorithm has the most complete time under
of parallel algorithm, an OpenMP program started the condition of 2 cores 4 threads, and the improved
from a single thread, need parallel program is derived algorithm has the least finish time under the condi-
at some point in the program (Fork) of some thread tion of 4 cores 8 threads, it is in accordance with the
group,the parallel code executed in parallel area, above rule.
and connected together (Join)in different threads at Then, comparison of serial algorithm under 4
the end of the parallel region when all threads in the cores 8 threads and improved algorithm under 2 cores
thread group is ends. OpenMP is Fork - Join model 4 threads will found that serial algorithm has less
work. In the above experiments, parallel work per- completed time when the number of node K <7000.
formed by OpenMP tools. Because of the advantages of hardware, serial algo-
4.3. The result of the experiment rithm faster than improved of parallelize algorithm.
In order to better explain the experimental results, But when the node number K continues to increase,
we compare algorithm in two aspects: on the one the advantage of improved algorithms become obvi-
hand, under the same conditions, compared the total ous, its speed can even faster than 4 cores serial al-
completion time of serial algorithm and improved of gorithm.
parallelize algorithm comparison; On the other hand, Conclusions
in the case of different cpus, compared the total com- Traditional algorithm optimization is under the
pletion time of two algorithms. By the experiments, premise of performance stability of processor, en-
the total completed time on the basis of the compari- hance operation efficiency as much as possible by
son research, the experimental data is shown in fig- changing the method to calculate or storage means.
ure 6. İmproved of parallelize algorithm in speed has But that changed with the emergence of multi-core
the obvious improvement, speed increased about by processors. Due to difficult of hardware performance
50%. improved, the number of software algorithm optimi-
Figure 7 shows the comparison of the completion zation should be transferred to the number of CPU.
time of improved of parallelize algorithm and serial At present, because of the influence of traditional

Figure 7. Improved Algorithm Compared with Serial Algorithm on Different Plant

80 Metallurgical and Mining Industry No. 9 — 2015

 Automatization
programming ideas, the development of the parallel Mode OpenMP/MPI Implementations, In-
software far behind the development of the parallel ternational Journal of Parallel Programming,
computing architecture. In this paper, the improved 2010, Vol. 38, p.p. 396-417.
of parallelize Dijkstra’s algorithm on multi-cores can 5. Neetesh Kumar, Deo Prakash Vidyarthi, Im-
greatly increase calculation efficiency. it can improve proved scheduler for multi-core many-core
computing speed by 50% when number of nodes is systems, Computing, 2014, 96, p.p.1087-1110.
huge. It provides a broad application space for im- 6. Seth Pettie, A new approach to all-pairs short-
proved ofparallelized Dijkstra’s algorithm in the field est paths on realweighted graphs[J], Theoreti-
of GIS with Multi-cores processors applications on cal Computer Science, Spacial Issue on Papers
embedded system. From I CAL P, 2002, 312(1), p.p.47-74.
7. zwick U, All pairs shortest paths using bridging
Acknowledgements sets and rectangular matrix multiplication[J].
This work is supported by the Foundation of Jilin ACM, 2002, 49, p.p.289-317.
Province Education Department (2014645). 8. Shiming Wang, Jianping Xing, Yong Wu,
Yubing Wu, Wei Xu, Xiangzhan Meng, Li-
References ang Gao, Double-Sources Dijkstra Algorithm
1. Tangwen wu, Shixiao dong, Zhuda kui, The within Typical Urban Road Networks, Ad-
Caculation of the Sortest Path Using Modi- vances in Computer Science and Education
fied Dijkstra Algorithm in GIS, Journal of Im- Advances in Intelligent and Soft Computing,
age and Graphics, 2000.12, Vol5(A), No.12, 2012, Vol 140, p.p. 155-161.
p.p.1019-1023. 9. Sathi Mukherjee, Dijkstra's Algorithm for
2. Liu Zhiyu, Yang Liu, Applying Improved Solving the Shortest Path Problem on Net-
Dijkstra Algorithm to Embedded GIS Syes- works Under Intuitionistic Fuzzy Environ-
tem, Computer Applications and Software, ment, Journal of Mathematical Modelling and
2009.12, Vol 26, No. 12. p.p.262-263. Algorithms, 2012, 12, Vol 11, Issue 4, p.p.345-
3. Li Qing, Xie Sijiang, TongXinhai, Wang Zhil- 359.
iang, A Self-adaptive genetic algorithm for the 10. Daniel Delling, Time-Dependent SHARC-
Shortest Path Planning of vehicles and its com- Routing, Algorithmica, 2011,5, Vol60, Issue
parison with Dijkstra and A* algorithms, Jour- 1, p.p. 60-94.
nal of University of Science and Technology 11. Kazuo Murota, Akiyoshi Shioura, Dijkstra's
Beijing, Nov.2006, Vol  28, No.11, p.p.1082- algorithm and L-concave function maximiza-
1086. tion, Mathematical Programming, 2014, 6,
4. J. M. Bull, J. Enright, X. Guo, C. Maynard and Vol 145, Issue 1-2, p.p.163-177.
F. Reid, Performance Evaluation of Mixed-

No. 9 — 2015 Metallurgical and Mining Industry 81