Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
V
o
l.
5, N
o
. 4
,
A
ugu
st
2015
, pp
. 77
2
~
78
1
I
S
SN
: 208
8-8
7
0
8
7
72
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
A P
a
th-
C
ompression Approach
for Improving Shortest-Path
Algorith
ms
Nabil Arma
n*, Fa
isa
l
Khama
y
s
eh**
* Department of
Computer Scien
ce
and
Engine
eri
ng, P
a
l
e
s
tine
P
o
l
y
t
echn
i
c Univ
ers
i
t
y
,
P
a
les
t
ine
** Departmen
t
o
f
Information
Technolog
y
,
Pa
lestine Poly
techn
i
c
University
, Palestine
Article Info
A
B
STRAC
T
Article histo
r
y:
Received
Ma
r 2, 2015
Rev
i
sed
Ap
r
23
, 20
15
Accepted
May 18, 2015
Given a weighted directed graph G=
(V;E;w), where w is n
on-negativ
e
weight function, G’ is a graph obtain
e
d from G b
y
an app
lication of path
compression. Path compression reduces
the gr
aph G to a crit
ica
l
set of
verti
ces
and
ed
ges
that
aff
ect
the gen
e
ra
tion
of s
hortes
t
tr
ees
. Th
e m
a
in
contribution of
this paper
is finding
shortest path
between two
selected
vertices b
y
apply
i
ng
a new alg
o
rith
m that r
e
d
u
ces number of nodes that
needs
to b
e
trav
ers
e
d in th
e gr
ap
h while
pr
eserving all gr
aph pro
p
erties. Th
e
main method of the algorithm is restru
cturing the graph in a way
th
at on
ly
critical/relev
ant
nodes are considered wh
ile all other neutr
a
l v
e
rtices and
weights ar
e pres
erved
as sub paths'
pr
oper
ties
.
Our algorithm can compress
the graph paths
into consider
abl
e
im
pr
oved perc
entag
e
es
peci
al
l
y
when the
graph is sparse
and hence
impr
oves performance s
i
gnificantly
.
Keyword:
C
o
m
m
uni
cat
i
o
n net
w
or
k
Graph
Represen
tatio
n
Path C
o
m
p
ression
Rev
e
rse Represen
tatio
n
Shortest Pat
h
Copyright ©
201
5 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
Faisal
T. Kha
m
ayseh,
Depa
rt
em
ent
of I
n
fo
rm
ati
on
Tech
nol
ogy
,
C
o
l
l
e
ge
of
I
n
f
o
rm
ati
onTec
hn
o
l
ogy
a
n
d
C
i
m
p
ut
er E
n
gi
nee
r
i
n
g
Palestin
e Po
lytech
n
i
c
Un
iv
ersity,
Hebro
n
, Palest
in
e.
Em
a
il: faisal@p
pu
.edu
1.
INTRODUCTION
Efficient approach of the si
ngle
so
ur
ce shor
test p
a
th
p
r
oble
m
o
n
co
mmu
n
i
cation
or tran
sp
ortatio
n
n
e
two
r
k
s
is ex
t
r
em
el
y i
m
p
o
r
tan
t
requ
irem
en
t for
real-world
ap
p
lication
s
.
Sin
ce find
ing
sh
ortest p
a
th
s
o
v
e
r n
e
t
w
ork
t
o
po
log
y
is exp
e
nsiv
e, it is worth
y
to
consid
er v
a
riou
s
tech
n
i
qu
es and h
e
u
r
istics th
at
can
h
e
lp
i
n
imp
r
ov
ing
th
e ex
i
s
tin
g
al
g
o
rith
ms. Th
e m
o
st well-k
nown algo
rith
m
fo
r fi
ndi
ng
a s
i
ngl
e-s
o
urce
s
h
o
r
t
e
st
pat
h
i
s
Di
j
k
st
ra'
s
al
g
o
ri
t
h
m
[1]
.
A
l
a
rge
vari
et
y
a
p
p
r
oaches
ha
v
e
bee
n
pr
o
pose
d
at
t
e
m
p
ti
ng t
o
i
m
prove t
h
e pe
rf
or
m
a
nce of s
h
ort
e
st
pat
h
al
g
o
ri
t
h
m
s
usi
ng
di
ff
erent
ass
u
m
p
t
i
ons
a
n
d
gra
p
h re
prese
n
t
a
t
i
ons [
2
]
-
[
1
0
]
. Thi
s
pa
per a
d
d
r
esses t
h
e v
a
l
u
e of t
h
e g
r
a
ph
rep
r
ese
n
t
a
t
i
on
- i
n
t
h
e f
o
r
m
of
com
p
ressi
o
n
gr
aph
-
t
o
i
m
prov
e t
h
e
per
f
o
r
m
a
nce
of
t
h
e s
h
or
t
e
st
pat
h
al
go
ri
t
h
m
.
Fin
d
i
n
g
th
e
sho
r
test
p
a
th
v
a
ries in
tim
e co
m
p
lex
i
t
y
u
p
o
n
th
e co
nstrain
t
s is to
b
e
applied
.
Su
ch
exam
pl
es are fi
n
d
i
n
g t
h
e si
ngl
e
-
so
u
r
ce sh
ort
e
st
pat
h
, si
ngl
e
-
so
u
r
ce sh
ort
e
st
pat
h
wi
t
h
t
h
e p
o
ssi
bi
l
i
t
y
of
n
e
g
a
tiv
e
weigh
t
s, k-shortest p
a
th
s, sing
l
e
-p
air
u
s
in
g
h
e
uristics, all-p
a
irs sh
or
test paths, etc.
These
assum
p
t
i
ons a
nd c
onst
r
ai
nt
s m
a
y
requi
re appl
y
i
n
g
si
m
p
l
e
m
i
nim
u
m
spanni
ng t
r
ee p
r
o
cedu
r
es t
o
ef
fe
ct
i
v
el
y
find
th
e sho
r
test p
a
th
,
wh
ile oth
e
r assu
m
p
tio
n
s
m
a
y req
u
i
re ad
van
c
ed
algorith
m
s
su
ch
as
Dijk
stra's alg
o
rith
m
.
Som
e
vari
at
i
o
n
s
and i
m
pro
v
e
m
ent
s
based
o
n
t
r
ee st
r
u
ct
u
r
e
s
have
bee
n
p
r
esent
e
d i
n
t
h
e l
i
t
e
rat
u
re. E
x
a
m
pl
e of
suc
h
va
riations is the running tim
e
based
on
Fibonacci
-heap m
i
n-priority queue
wh
i
c
h is O(|V|log|V|+|E|)
assum
i
ng t
h
at
w(e
)
i
s
a
n
o
nne
gat
i
v
e
wei
g
ht
[
1
]
.
Recent resea
r
ch atte
m
p
t to im
prove shortest path
algorithm based on sea
r
ch strate
gy by introduci
ng
a const
r
ai
nt
f
u
nct
i
on
wi
t
h
we
i
ght
ed
val
u
e a
nd i
g
n
o
ri
ng t
h
e l
a
rge n
u
m
b
er
of i
r
rel
e
va
nt
n
ode
s d
u
ri
ng s
h
ort
e
st
pat
h
fi
ndi
ng [
1
1]
. Som
e
researche
r
s ha
ve f
o
cuse
d
m
o
re o
n
overc
om
i
ng t
h
e net
w
or
k st
r
u
ct
u
r
e rat
h
e
r
t
h
an t
h
e
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
77
2
–
78
1
7
73
algo
rithm
itself.
Refere
nces
[1
2]
-[
14
] p
r
esen
ted
an
al
g
o
rith
m
to
fin
d
th
e sh
ortest p
a
th
throug
h
g
r
aph
p
a
rtitio
n
i
n
g
. Th
ey to
ok
an
adv
a
n
t
ag
e
o
f
ro
ad
n
e
t
w
ork
f
eat
u
r
es t
o
im
p
r
o
v
e th
e search
.
Th
e m
a
in
featu
r
e is th
e
pos
sibility of partitioni
ng t
h
e gra
ph i
n
to a
set of c
o
m
ponents
or cl
usters. T
h
ey focus
e
d on sim
p
lifying t
h
e
detailed gra
ph by clustering nodes that are near each
other. In the fi
nal gene
rated
gra
p
h, the sea
r
ch is
con
d
u
ct
ed
nea
r
t
h
e st
art
o
f
t
h
e
dest
i
n
at
i
o
n
o
f
t
h
e pat
h
a
n
d
a
m
ong t
h
e c
o
m
p
o
n
e
n
t
s
on
t
h
e
t
r
ansi
t
ed
ges
.
The
fi
rst
se
ct
i
on
of t
h
i
s
p
a
per
desc
ri
bes
an e
x
i
s
t
i
n
g t
e
chni
que
o
f
gra
p
h
re
pres
ent
a
t
i
o
n
an
d
h
o
w
th
is techn
i
qu
e
works
o
n
p
a
t
h
ex
isten
c
e
in directed weighted gra
p
hs
[2].
Th
e
rem
a
in
in
g sectio
n
s
presen
t ou
r
al
go
ri
t
h
m
and
i
t
s
im
prov
em
ent
s
. T
h
i
s
wo
r
k
prese
n
t
s
a
n
e
w i
m
prove
d
vari
at
i
o
n
of
fi
ndi
ng
si
n
g
l
e
s
o
u
r
ce-
d
e
stin
ation
sh
ortest p
a
th b
y
focu
sing
on
co
mp
ressi
on
g
r
ap
h.
Let
G=(
V
;
E
;
w
)
be a
di
rect
ed
gra
p
h, a
n
d
G'
=(V;
E'
;
w
)
t
h
e c
o
m
p
ressed
g
r
ap
h
w
h
i
c
h
f
o
rm
ed f
r
om
G,
wh
ere V is
a set of
v
e
rtices, E is
a set
o
f
edge
s ,
E'
a set
o
f
e
dge
s f
o
rm
ed
usi
n
g c
o
m
p
ressi
o
n
fu
nct
i
o
n a
n
d
w is the weight function, where w(e
)
> 0 for each e
dge e
E. Let each edge e has a non-ne
gative
weight.
Assum
e
<s> and <t> are
gi
ven
ve
rtices
where
<s> a
n
d
<t>
V, <s>
is
the s
o
urce
ve
rtex a
n
d <t> i
s
the
d
e
stin
ation
.
Th
e sing
le p
a
i
r
so
urce-d
e
stin
ati
o
n
sho
r
test
p
a
th
is to
fi
n
d
th
e
p
a
th
with
th
e
min
i
m
u
m
co
st
su
m
o
f
edge
s f
r
o
m
sou
r
ce <s> t
o
dest
i
n
at
i
on <t
>
.
Fi
gu
re 1.
G
r
ap
h G=(
V
;
E
;
w
)
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
A Pat
h
-C
om
pr
essi
on
A
ppr
o
a
c
h f
o
r I
m
pr
ovi
n
g
S
h
o
rt
est
-
P
a
t
h
Al
g
o
ri
t
h
ms
(
N
abi
l
Ar
m
an)
77
4
2.
REPRESE
N
T
A
TIO
N
AN
D DAT
A
ST
R
U
C
TU
RE
A grap
h G=(V;E;w) co
n
s
isti
n
g
of a set
o
f
|V| n
on
-re
peat
able ve
rtices, requi
res two matrices wit
h
m
a
x
i
mu
m |
V
|
2
el
em
ent
s
t
o
represe
n
t
t
h
e
gr
aph i
n
n
o
rm
al and
reve
rse r
e
prese
n
t
a
t
i
o
ns
[2]
.
Fi
gu
re 1
depi
ct
s
gra
p
h G=(
V
;
E
;
w
)
whi
c
h i
s
represe
n
t
e
d i
n
t
h
e
m
a
t
r
i
x
st
ruct
ure a
nd l
i
n
ea
r array
as sh
o
w
n
i
n
Tabl
e 1 an
d
Tabl
e
3
res
p
ectively.
These represe
n
tations we
re use
d
in de
vel
o
pi
n
g
pa
ral
l
e
l
al
go
ri
t
h
m
s
for t
h
e ge
ne
ral
i
zed
sam
e
gene
rat
i
o
n que
ri
es
i
n
de
duct
i
ve dat
a
bases
[
4
]
.
Tabl
e 1. Gra
p
h
M
a
t
r
i
x
R
e
pres
ent
a
t
i
on f
o
r G
r
aph
G
-
-
0 1 2 3 4
5 6 7 8 9 10
0
v1
v2
v4
v10
v12
v18
v51
v52
v54
1
v55
v59
v60
2
v5
v6
v11
0,
4
3
v20
v19
v27
v35
v58
1,
9
4
v
3
4
3
,
9
5
v53
3,
8
6
v22
v21
v26
v28
v31
v33
7
v29
v30
v32
6,
9
8
3
,
7
9
v7
v8
v9
v23
10
v
2
4
v
2
5
11
v
3
0
,
2
12
v37
v38
v14
v13
v17
v50
v49
v56
v57
1,
8
13
v36
v39
v43
v15
12,
5
14
v40
v41
v45
v46
v48
15
v16
v47
12,
7
16
1
4
,
5
17
v42
v44
13,
3
18
1
5
,
4
The re
ver
s
e m
a
t
r
i
x
re
prese
n
t
a
t
i
on o
f
t
h
e g
r
aph
G i
s
de
pi
ct
ed i
n
Tabl
e
2. T
h
i
s
st
ruct
u
r
e hel
p
s i
n
fi
n
d
i
n
g al
l
pos
si
bl
e ancest
o
r
vert
i
ces st
art
i
n
g f
r
om
a dest
i
n
at
i
on
n
ode <t
i
>
. For e
x
am
pl
e, vert
e
x
<v
6
0
> i
s
reacha
b
le from
node
<v1> via
<v2, v4, v5
, v6, v11, v20,
v19, v53, v35,
v34, v58>
.
For efficient im
ple
m
entation and to
sa
ve st
ora
g
e, t
h
e m
a
tr
ix can als
o
be represe
n
ted as a
linear array
with
|E| en
tries.
The ad
va
nt
age
of re
prese
n
t
i
n
g t
h
e gra
p
h i
n
grap
h m
a
t
r
i
x
i
s
st
ori
ng al
l
p
a
t
h
s fr
om
every
possi
bl
e
v
e
rtex
to
all
reach
ab
le
v
e
rtices in
th
e graph
.
Th
is
way
o
f
r
e
prese
n
t
a
t
i
o
n pr
o
v
i
d
es
a
set
of be
nefi
t
s
. It
t
a
kes
a
linear tim
e
to check t
h
e pat
h
ex
isten
ce.
It also
h
e
l
p
s in
find
ing
sim
p
le
sub bat
h
s of
vert
ices of in-degree and
out
-de
g
ree
o
f
1. T
h
i
s
re
pres
ent
a
t
i
on al
s
o
s
h
o
w
s al
l
g
r
ap
h
ro
ot
s an
d
pat
h
s'
ends i
n
re
fer
e
nce t
o
a
gi
ve
n
sou
r
ce
verte
x
is. Zero
in-degree ve
rtices ar
e shown
in
th
e first co
lum
n
(th
e
so
ur
ce
s colum
n
). Pat
h
s are
represe
n
ted in
as a de
pt
h fi
rs
t
search t
r
a
v
e
r
sal
or
der
w
h
i
l
e
com
m
on par
t
s of t
h
e
pat
h
s
are st
o
r
ed
o
n
l
y
once u
s
i
n
g
array
i
nde
xi
n
g
t
o
avoi
d d
u
p
l
i
cat
i
ons o
f
s
u
b
p
a
t
h
s. F
o
r e
x
a
m
pl
e, i
f
pat
h
s p1 i
s
rep
r
esent
e
d as
v
e
rt
i
ces
<v
1,v2
,v
i,…,vn
-1
,vn
>
an
d p2
is <v1
,
v2
,..,v
i
,..,v
m
>
, P1 an
d P2
ar
e
p
r
esen
t in th
e
gr
aph
,
t
h
en
p
2
is st
o
r
ed
i
n
th
e n
e
x
t
row
of p1
starting
fro
m
th
e
co
lu
mn
(i+1) represen
tin
g
t
h
e rest
o
f
th
e
p2
as <v
i+1
,
v
i
+2, …> with
e
m
p
t
y i+1
en
tries.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
77
2
–
78
1
7
75
Tab
l
e
2
.
Rev
e
rse Matrix
Rep
r
esen
tatio
n fo
r
Graph
-
-
0 1
2
3 4
5
6 7
8
9
10
11
0 v23
v9
v8
v7
v2
v1
1
v25
v24
0,
1
2
v33
v31
v28
v26
v21
v22
v6
v5
0,
4
3
v32
v30
v29
2,
3
4
v48
v16
v44
v42
v40
v36
5
v45
v41
4,
4
6
v46
5,
2
7
v54
v52
v51
v18
v12
v10
v4
0,
4
8
v3
0,
5
9
v11
2,
6
10
v60
v58
v34
v35
v53
v19
v20
9,
5
11
v27
10,
5
12
2,
4
13
10,
3
14
v59
v55
7,
2
15
v57
v56
v49
v50
v17
v13
v14
v38
v37
0,
5
16
v15
v43
v39
4,
5
17
4,
2
18
v47
4,
1
Tabl
e
3. Li
near
array
re
prese
n
t
a
t
i
on f
o
r
g
r
a
p
h
Node Refer
e
nce
Node
Refer
e
nce
Node
Refer
e
nce
0,
0
v1
5,
8
3,
8
12,
6
v50
0,
1 v2
6.
4
v22
12,
7
v49
0,
2
v4
6.
5
v21
12,
8
v56
0,
3 v10
6.
6
v26
12,
9
v57
0,
4
v12
6.
7
v28
12,
10
1,
8
0,
5 v18
6.
8
v31
13,
0
v36
:
:
:
:
:
:
:
:
:
:
:
:
4,
8
v34
12,
3
v14
18,
4
15,
4
4,
9 3,
9
12,
4
v13
5,
7
v53
12,
5
v17
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
A Pat
h
-C
om
pr
essi
on
A
ppr
o
a
c
h f
o
r I
m
pr
ovi
n
g
S
h
o
rt
est
-
P
a
t
h
Al
g
o
ri
t
h
ms
(
N
abi
l
Ar
m
an)
77
6
Tabl
e 4.
C
o
m
p
resse
d-
wei
g
ht
ed gra
p
h
re
p
r
es
ent
a
t
i
o
n
-
-
0
1
2
3 4
5 6
7
8 9
10
0
v1
-
v2
5
v4
v10
v12
v18
v51
v52
v54
v
1
1
v55
v59
v60
2
v5
v6
15
v11
16
0,
4
v2
v5
v6
3
v20
20
v19
22
v27
26
v35
28
v58
33
1,
9
37
v11
v20
v19
v27
v35
v58
4
v34
3,
9
5
v53
3,
8
6
v22
v21
v26
v28
v31
v33
7
v29
v30
v32
6,
9
8
3,
7
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
18
15,
4
3.
PATH CO
MP
RESSI
ON
Fi
gu
re 2 sh
ow
s
t
h
e
c
o
m
p
res
s
ed gra
p
h G’=
(
V,
E,
w'
)
aft
e
r
doi
ng
s
o
m
e
pr
ocessi
n
g
/
c
om
pressi
o
n
o
n
gra
p
h G=(
V
,E
,
w
) t
o
red
u
ce t
h
e n
u
m
b
er of no
des an
d ed
g
e
s neede
d
t
o
b
e
consi
d
e
r
e
d
i
n
com
put
i
ng
p
a
t
h
s as
sho
w
n t
a
bl
e 4
.
For e
x
am
pl
e, t
h
e sh
o
r
t
e
st
pat
h
f
r
om
vert
ex
<v1> t
o
ve
rt
ex
<v6
0
>
on
Gra
ph
G i
n
Fi
gu
re
1 i
s
3
7
and t
h
e pat
h
i
s
<v1
,
v
2
,
v
5
,
v
6
,
v1
1,
v
2
0
,
v
1
9
,
v
2
7
,
v3
5,
v5
8,
v
60>
. A
n
d al
so t
h
e sh
o
r
t
e
st
pat
h
f
r
om
vert
e
x
<v1>
t
o
ve
rt
ex
<v
60>
o
n
G'
i
s
3
7
but
t
h
e
pat
h
i
s
c
o
m
p
resse
d as
<v
1,
v
2
,
v
6
,
v
1
1
,
v1
9,
v
3
5
,
v
60>
.
4.
SHORTEST PATH US
ING COMPR
E
SSION
Thi
s
o
p
t
i
m
i
zed t
echni
qu
e m
a
y
excl
ude hu
ge pa
rt
s o
f
t
h
e gra
ph a
n
d he
nce saves
t
h
e cost
an
d
im
pro
v
es
per
f
o
r
m
a
nce of t
h
e
gra
p
hs.
The
t
echni
que
i
s
s
u
m
m
a
ri
zed as:
1)
Co
n
s
t
r
u
c
t th
e
matrix
to
rep
r
esen
t th
e
graph
with
in
ner s
t
ructure that i
n
cludes
the
V
e
rtex,
Dist, P
r
ed
No
de,
Di
rect
P
a
t
h
t
h
at
ha
ve
a 0/
1
fl
a
g
,
G
o
al
No
de, a
n
d a
ccum
u
l
a
t
e
d w
e
i
ght
s
fr
om
Di
rect
Pat
h
.
Di
st
[v]
main
tain
s th
e
min
i
m
u
m
d
i
sta
n
ce to <v
> v
i
a
Pred
Nod
e
.
2)
Trave
r
se t
h
e g
r
aph
G t
o
st
o
r
e
di
rect
pat
h
s
fo
r
no
des
w
h
ere
o
u
t
D
e
g
ree
[
N
o
d
e
]
equal
1 an
d
i
n
De
gree
[N
o
d
e
]
equal
1
a
s
:
St
ore
t
h
e
N
ode
pa
rent
,
w
h
ere
out
Deg
r
ee[
pa
r
e
nt
]
eq
ual
1
.
Fi
nd
t
h
e
Goal
No
de,
t
h
e
fi
rst
n
ode
we
reac
hed
i
t
t
h
at
has
out
Deg
r
ee[
N
o
de]
n
o
t
eq
ual
1 i
n
t
h
e sam
e
pat
h
.
St
ore
Di
rect
Pa
t
h
bet
w
een
t
h
e
pare
nt
a
n
d
the
Goal
Node, and the acc
um
ulated
weight.
3)
C
onst
r
uct
t
h
e
R
e
verse
M
a
t
r
i
x
t
o
re
pre
s
ent
t
h
e
gra
p
h r
o
ot
ed
wi
t
h
dest
i
n
at
i
ons
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
77
2
–
78
1
7
77
Fig
u
r
e
2
.
Co
mp
r
e
ssed gr
aph
4)
Trave
r
se
t
h
e g
r
ap
h G
st
a
r
t
i
n
g by
t
h
e gi
ve
n
dest
i
n
at
i
o
n
t
o
m
a
rk
all can
did
a
te no
d
e
s in
th
e m
a
in
m
a
tri
x
rep
r
ese
n
t
a
t
i
on.
Thi
s
i
s
possi
b
l
e usi
ng R
e
ver
s
e M
a
t
r
i
x
m
a
rki
n
g al
l
candi
dat
e
no
des as
di
scuss
e
d i
n
t
h
e
al
go
ri
t
h
m
.
Thi
s
i
s
al
s
o
pos
si
bl
e i
n
di
ffe
ren
t
way
s
as pref
erre
d by
t
h
e p
r
o
g
ram
m
er, e.g., c
opy
i
n
g t
h
e
candi
dat
e
n
ode
s t
o
a di
ffe
re
nt
red
u
ced m
a
t
r
i
x
,
havi
ng a m
a
rk
fl
ag i
n
t
h
e
n
ode st
ruct
ure,
or
by
cha
ngi
n
g
th
e wei
g
h
t
s
of
th
e ex
cl
u
d
e
d
no
d
e
s to
i
n
fi
n
ity in
th
e m
a
in
grap
h m
a
trix
. The p
r
eferred
way is to
h
a
v
e
a
0/1
fl
ag i
n
a c
o
r
r
es
po
n
d
i
n
g c
o
o
r
di
na
te lin
ear array represen
tatio
n
.
5)
After m
a
rk
ing th
e can
d
i
d
a
te su
bg
raph
in
t
h
e m
a
in
m
a
tr
i
x
, an
d
star
ting f
r
o
m
th
e g
i
ven
sour
ce s, th
e
algorithm
check if ther
e
exist
a DirectPat
h
.
If t
h
ere ex
ists
a Direct
Path
,
we
d
i
rectly tak
e
th
e
di
rect paths; else we
add all nei
g
hbor edges
by
vi
si
t
i
ng al
l
no
des l
i
s
t
e
d i
n
t
h
e ne
xt
col
u
m
n
(b
rea
d
t
h
fa
sh
io
n)
o
f
th
e cu
rren
t
nod
e (v
ertex
)
. In
t
h
is case, we
always accum
u
late the subpath
weight by
a
d
ding the
curre
nt verte
x
weight
to
acc
um
ulate
d
path weight (dist).
Whe
n
e
v
er
we r
ead t
h
e co
o
r
di
nat
e
s (i
,
j
) o
f
an
y
vert
ex, i
t
m
e
ans t
h
at
we re
v
i
si
t
t
h
e node
us
i
ng an
ot
her
edge
e with new wei
g
ht w(e
)
. In t
h
is case
we di
rectly
ju
m
p
t
o
coo
r
di
n
a
t
e
s'
poi
nt
er
(i
,j
) i
n
t
h
e m
a
i
n
gra
p
h
m
a
t
r
i
x
as re
pre
s
ent
e
d i
n
Ta
bl
e
1 a
n
d
com
p
are
t
h
e
new
wei
g
h
t
s and
he
nce
w
e
kee
p
t
h
e
m
i
nim
u
m
pat
h
di
st
ance
with updated
predeces
sor nodes.
The al
go
ri
t
h
m
Sh
ort
e
st
Pat
h
Usi
n
g Pat
h
C
o
m
p
ressi
on
fi
n
d
s
t
h
e s
h
ort
e
st
pat
h
base
d
on
red
u
ci
n
g
t
h
e
num
ber of edges and nodes
that
m
a
ke the search take
l
e
ss tim
e
than searchi
ng i
n
th
e en
tire graph
.
Th
is
efficien
t
p
r
o
c
ed
ure sav
e
s m
u
ch
work
co
m
p
aring
to th
e
fu
nctio
n
a
lity o
f
kno
wn
con
v
e
n
tion
a
l algo
rith
m
s
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
A Pat
h
-C
om
pr
essi
on
A
ppr
o
a
c
h f
o
r I
m
pr
ovi
n
g
S
h
o
rt
est
-
P
a
t
h
Al
g
o
ri
t
h
ms
(
N
abi
l
Ar
m
an)
77
8
Algorithm Shortest_Path_Using_Candi
dat
e
s
(Graph, M
a
r
k
, Rever
se_M
atrix)
{in
itia
lize Ma
rk[i
]
t
o
0
N
ode
=t
Mark[
N
ode
]
=
1
for every ve
rtex next to Node
in Reverse
_M
atrix
i
f
vert
ex !
=
c
oor
di
nat
es
_p
oi
nt
er
N
ode
=vert
e
x
else
N
ode
=Re
verseMat
r
i
x
[
c
oor
di
nat
es
_p
oi
nt
er
]
Mark[
N
ode
]
=
1
e
n
d if
end for
dist= Fi
ndShortest(GraphM
a
trix, Mark
, s)
}
Functio
n FindSho
rtest
(GraphMa
trix
,M
a
r
k,s)
{
for e
a
ch vertex
v in
Gr
aphM
atrix
d
i
st[v
]
=
in
fin
it
y;
pre
d
[
v
]
=
u
ndef
i
ned
;
end for
di
st
[
s
]
:
=
0 ;
Mark
Q=set
of
Marke
d
no
des
i
n
Gr
a
p
h
M
at
ri
x
or
dere
d as of
de
pt
h
f
i
rst
se
a
r
ch
vi
si
t
s
.
while Mark
Q i
s
not e
m
pty
and
u !
=
t
:
u
=
vertex in Ma
rkQ with
smallest d
i
sta
n
c
e in
d
i
st[
]
;
remove u
from Mark
Q;
if (u
== t ||d
i
st[u
]
== in
fin
ity)
bre
a
k
;
en
d if
find
co
ord
i
na
tes f
o
r v
if ( th
ere is a
d
i
rect pa
th fo
r
n
o
d
e
)
for
ea
ch goa
lNod
e in G
r
ap
hMa
t
rix
an
d
goalNode
is in MarkQ
p
=
di
st
[
u
]
+
di
st
_bet
w
een
(
u
,
g
o
a
l
N
o
d
e)
;
i
f
(
p <
d
i
s
t
[
goal
N
o
de
]
)
di
st
[
goal
N
ode
]=p
;
p
r
ed
[g
oa
lNod
e]
=u
;
e
n
d if
e
n
d for
e
n
d if
fo
r
ea
ch
n
e
ig
hbo
r
v o
f
u
and
v
is in
Ma
r
k
Q
if v is coo
r
d
i
na
te po
in
ter
<a,b>
v=G
r
ap
hMa
t
rix[a
,
b
]
e
n
d if
p=dist[
u
]
+ dist_between(
u
, v)
;
ifp<
d
ist[
v
]
:
di
st
[
v
]
=
p
;
pre
d
[
v
]
=
u
;
update v i
n
M
a
rkQ
;
end if
e
n
d for
en
d wh
ile
return dist;
}
5.
PERFO
R
MA
NCE IMP
R
O
V
EME
N
T
An
al
g
o
ri
t
h
m
that
fi
nds
t
h
e s
h
ort
e
st
pat
h
P(s
,
t
)
bet
w
een t
w
o
gi
ve
n
vert
i
ces
<s> an
d <t
> i
n
a di
rect
e
d
weig
hted g
r
a
p
h G
(
V,
E,
w) is prese
n
te
d. It clearly determ
in
es the com
p
re
ssed g
r
ap
h G'
(
V
'
,
E'
,w). T
h
i
s
o
b
v
i
o
us
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
77
2
–
78
1
7
79
im
pro
v
em
ent
reduce
s
t
h
e
nu
m
b
er of ed
ges
|
E
|
and ve
rt
i
ces
|
V
|
i
n
t
h
e g
r
ap
h w
h
i
c
h l
o
we
r
s
t
h
e cost
. E
q
u
a
t
i
on1
DC(E
) calc
u
la
tes the
degree
of com
p
ressi
on in term
s of ve
rtices and edges
.
DCE
#
#
∗
100%
DCE
|
|
∗
100%
(1
)
Havi
ng
G
r
ap
h
G di
pect
ed i
n
Fi
gu
re
1
whi
c
h
has a
di
rect
pat
h
P
fr
om
v37
t
o
v
17
w
h
e
r
e p={
v
37
,
v3
8,
v1
4, v
1
3
,
v1
7} an
d P ha
s 4 edges
,
as i
m
provem
e
nt
on t
h
i
s
pat
h
, w
e
have a di
rect
edge f
r
o
m
v37
t
o
v17
.
Thi
s
m
eans t
h
at
we r
e
d
u
ce
d
t
h
e n
u
m
b
er
of
edge
s f
r
o
m
4 edge
s t
o
o
n
e e
d
ge.
If
t
h
e
de
gr
ee o
f
c
o
m
p
ressi
on i
s
use
d
,
we get
7
5
% t
i
m
e savi
ng.
If
we l
o
ok a
t
t
h
e ent
i
r
e g
r
a
ph
G, i
t
ha
s a
t
o
t
a
l
num
ber o
f
ed
ges e
qual
s
t
o
7
1
edge
s.
Aft
e
r c
o
m
p
ressi
n
g
i
t
t
o
gra
p
h
G
’
as i
l
l
u
st
rat
e
d i
n
Fi
gu
re
2,
t
h
e
ne
w
n
u
m
b
er
of
edge
s i
s
4
6
.
A
ppl
y
i
n
g
t
h
e com
p
ressi
o
n
eq
uat
i
o
n, t
h
e
gra
ph si
ze, t
h
e savi
n
g
rat
i
o
i
s
36%
. Thi
s
t
a
ngi
bl
e savi
n
g
i
s
dem
a
ndi
ng i
n
real
-
wo
rl
d
ap
pl
i
cat
i
ons
a
n
d
net
w
o
r
ks.
Each sh
o
r
t
e
st
pat
h
re
qui
re
s O(
(|
V|
+|
E|
)l
og |
V
|
)
usi
n
g
t
r
adi
t
i
onal
al
go
ri
t
h
m
s
m
a
k
i
ng t
h
e c
o
st
ext
r
em
el
y hi
g
h
. T
h
e p
r
o
p
o
s
e
d al
g
o
ri
t
h
m
int
r
od
uces m
o
re im
provem
e
n
t
s com
p
ari
ng
wi
t
h
som
e
l
a
t
e
st
udi
es
suc
h
as
t
h
e i
m
provem
e
nt
s i
n
t
r
od
uce
d
i
n
[
5
]
-
[
7
]
.
M
o
r
e
o
v
er
,
ou
r al
go
ri
t
h
m
wor
k
s i
n
bet
t
e
r a
n
d
i
m
pro
v
e
d
per
f
o
r
m
a
nce o
n
s
p
ars
e
a
n
d
de
nse
net
w
or
ks
.
The expe
rim
e
n
t
al phase provi
d
es evi
d
ence t
h
at th
e p
r
op
osed
h
e
u
r
istic outp
e
r
f
or
m
s
th
e co
nv
en
tio
n
a
l
algorithm
s
. The perform
a
nce
of the al
go
rithm is
co
m
p
ared
with
th
at o
f
the conventional proce
d
ure and shows
a consi
d
era
b
l
e
cost
savi
n
g
i
n
ra
nd
om
generat
e
d g
r
a
phs
wi
t
h
di
f
f
ere
n
t
si
zes ran
g
e fr
om
30 t
o
30
0
no
des
.
Savi
n
g
s i
n
per
f
o
r
m
a
nce occu
r i
n
de
nse
gra
p
hs a
n
d
m
o
re i
n
spa
r
se
one
s i
n
m
o
st
of t
h
e t
r
i
a
l
s
. Ta
bl
e 5
s
h
o
w
s
the pe
rform
a
nce savi
ng ratios
as a re
sult
of t
h
e experim
e
nt.
Tabl
e 5. Savi
n
g
rat
i
o
of pe
rf
o
r
m
a
nce
i
n
spa
r
se
an
d de
nse gr
aph
s
N
ode
s
Spar
se (%
)
D
e
nse (%
)
30
0
.
136
684
6
0
.
446
034
6
60
0
.
491
337
5 0
.
561
997
8
90
0
.
448
186
1
0
.
424
957
5
1
20
0
.
643
749
9 0
.
240
617
2
1
50
0
.
312
194
5
0
.
178
892
1
1
80
0
.
369
958 0
.
176
122
2
2
10
0
.
261
286
2
0
.
124
968
3
2
40
0
.
197
028
3 0
.
241
218
6
2
70
0
.
261
878
2
0
.
211
477
6
3
00
0
.
241
049
7 0
.
302
880
2
Fi
gu
res
3 a
n
d
4 s
h
ow t
h
e
avera
g
e
per
f
o
r
m
ance of
ap
pl
y
i
ng t
h
e i
m
pr
ove
d al
go
ri
t
h
m
on set
of
ran
d
o
m
l
y
generat
e
d g
r
ap
hs
wi
t
h
di
ffe
re
nt
densi
t
y
de
grees
. Thi
s
s
h
o
w
s t
h
at
t
h
e
pro
p
o
se
d al
go
ri
t
h
m
out
per
f
o
r
m
s
t
h
e st
andar
d
de
p
t
h-fi
rst
search
pr
oce
d
u
r
es o
n
t
h
e ori
g
i
n
al
gr
aph
.
Speci
fi
cal
l
y
, t
h
e conve
nt
i
onal
alg
o
rith
m
ap
p
lied
is
Dijk
stra’s.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
A Pat
h
-C
om
pr
essi
on
A
ppr
o
a
c
h f
o
r I
m
pr
ovi
n
g
S
h
o
rt
est
-
P
a
t
h
Al
g
o
ri
t
h
ms
(
N
abi
l
Ar
m
an)
78
0
Fig
u
r
e
3
.
Perfor
m
an
ce o
f
pr
opo
sed
algo
r
ith
m
on
sp
ar
se
g
r
aph
Fig
u
r
e
4
.
Perfor
m
an
ce o
f
pr
opo
sed
algo
r
ith
m
on
d
e
nse
g
r
aph
6.
CO
NCL
USI
O
N
For a gi
ve
n wei
g
ht
ed g
r
a
p
h G(
V,
E,
w),
wi
t
h
wei
g
ht
s
as a funct
i
o
n
of |
w
(e)|
, an e
ffi
ci
ent
an
d
im
pro
v
ed al
g
o
r
i
t
h
m
for fi
n
d
i
ng s
h
o
r
t
e
st
p
a
t
h
s bet
w
ee
n
a gi
ve
n so
urc
e
<s> and de
st
i
n
at
i
on <t
> usi
n
g
gene
rat
e
d
-
c
o
m
p
ress
ed
g
r
a
p
h
G'
have
been
prese
n
t
e
d
.
In
t
h
e
pract
i
cal
ph
ase, t
h
e
al
g
o
ri
t
h
m
out
pe
rf
orm
s
t
h
e
per
f
o
r
m
a
nce o
f
i
m
pro
v
ed
al
go
ri
t
h
m
.
It
s
h
ows
ob
vi
o
u
s
i
m
prove
d
per
f
o
rm
ance i
n
se
t
of
ra
n
dom
g
e
neral
ap
p
lied
graph
s
. As a h
e
uristic alg
o
rith
m
,
th
e co
m
p
lex
ity
w
i
l
l
alw
a
ys b
e
bou
nd
ed
b
y
th
e co
m
p
lex
ity o
f
kn
own
alg
o
rith
m
s
, ie., it will n
o
t
ex
ceed
O((|V|+|E|)lo
g
|
V
|).
ACKNOWLE
DGE
M
ENTS
Thi
s
resea
r
c
h
i
s
fu
nde
d
by
The Sci
e
nt
i
f
i
c
R
e
search C
o
unci
l
,
M
i
ni
st
ry
of E
d
ucat
i
o
n
and
Hi
ghe
r
Ed
ucat
i
o
n
,
St
a
t
e of Pal
e
st
i
n
e
un
de
r a p
r
oje
c
t
num
ber o
f
01/
12/
20
1
3
, a
n
d Pal
e
st
i
n
e P
o
l
y
t
echni
c U
n
i
v
ersi
t
y
.
The a
u
t
h
ors
w
oul
d l
i
k
e t
o
t
h
ank t
h
e
research assistants
Ms.
W
a
laa
Na
ser Idin a
n
d
Ms. Salm
a Dirbas
hi for
th
eir
h
e
lp
i
n
imp
l
em
en
tin
g
th
e alg
o
rith
m
s
.
0
5
10
15
20
0
3
0
6
0
9
0
120
150
180
210
240
270
300
Time
Nodes
Short
e
s
t
Pa
t
h
[
Spar
se
Gr
aph]
Dijkstra's
Algorithm
Compression
Algorithm
0
2
4
6
8
10
12
14
30
60
90
120
150
180
210
240
270
300
Time
Nodes
Short
e
s
t
Pa
t
h
[
Dense
Gr
aph]
Dijkstra's
Algorithm
Compression
Algorithm
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
77
2
–
78
1
7
81
REFERE
NC
ES
[1]
T.H. Cormen,
C
.
E. Leiserson,
R.L. Riv
e
st,
and
C. Stein
,
“Dijkstr
a'
s A
l
gorith
m. Introduction
to Algor
ithms”,
(Second ed
.). Section
24.3: pp. 5
95–601.
MIT
Press and McGraw-Hill
. ISBN 0-26
2-03293-7.
[2]
F. Kham
a
y
seh
and N. Arm
a
n,
“
A
n Efficien
t
Multiple
Sour
ce
Single Destin
at
ion (MSSD) He
uristic Algor
ith
m
Using Nodes Ex
clusions”,
International Journal of
Soft
Computin
g
, Vol. 10
, 2015
.
[3]
H.N. Djidjev
,
G.E. Pantziou, and
C.D. Zar
o
liagis
,
“Impro
ved Algorith
ms for Dy
n
a
mic Shortest Paths”,
Algorithmica
(2
000) 28: 367–38
9.
[4]
N. Arm
a
n, “
P
arall
e
l Algorithm
s
for the Genera
li
zed
Sam
e
Gener
a
tion Quer
y in
Deductiv
e Datab
a
ses”,
Journal o
f
Digital Information
Managemen
t
: 4(3), 192-
196,
2006,
ISSN 0972-72.
[5]
J.B. Orlin
, K
.
Kamesh Madduri, K
.
S
ubraman
i,
and M. Williamson, “A fast
er algor
ithm for
the sing
le sour
ce
shortest pa
th pro
b
lem
with f
e
w di
stinct
positiv
e l
e
ngths”
.
J. of Discrete Algorithms
, 8
,
2
(June 2010
), 189-198
[6]
L. Xiao
, L. Ch
en, and J. Xiao, “A new algorith
m
for shortest path problem in large-scale gr
aph
”
.
Appl. Math
, 6(
3),
(2012), 657-663
.
[7]
F. Zhang, A. Qiu, and Q. Li,
“Improve on Dijkstra Shortest
Path Algorithm for Huge Data”.
Chinese academy of
surveying and
m
apping
: Chin
a, 2
005.
[8]
F. Khamay
seh
and N. Arman,
“An Efficient
Heuristic Shortest Path
Algorith
m Using Candidate Subgraphs”.
International Co
nference on
Inte
lligent Systems a
nd Applications
.
Hammamet, Tun
i
sia. 22-24 Mar
c
h, 2014
.
[9]
F. Khamay
seh
and N. Arma
n. “Improvement of Shortest-Path Al
gorithms Using Subgraphs'
Heur
istics”,
Journal of
Theoretical and
Applied
Informa
tion Technology
, 2015. Vol. 76.
[10]
E.W. Dijkstr
a
,
“A note on Two Probl
ems in Connexion
with Graphs”,
Nume
risc
he
Mathe
m
atik
, 1: 26
9
271. doi:10.1007
/BF01386390.
[11]
Y.
Huang,
Q.
Yi,
and M. Shi,
“A
n Improved Dijkstra Shor
test Path
Algo
r
ithm”. Proceedings of the 2nd
International Co
nference on Computer
Science
and Electr
onics Engineering
(ICCSEE 2013).
Hangzhou, Chin
a,
Paris: Atlantis P
r
e
ss, March
201
3: 226-229.
[12]
F. Sim
e
k and I. Sim
ecek, “
I
m
p
r
ovem
e
nt of Shorte
st Path Algor
ithm
s
through Graph Partit
ionin
g
”.
Internationa
l
Confer
enc
e
Pr
es
entation
of
Math
ematics
. Liberec, Czech
Republic, 2011
.
[13]
W. Yah
y
a1
, A. Basuki2, J. Jiang.
“
T
he Exten
d
ed Dijks
t
ra’s
-b
as
ed Load
Balancing for Open Flow
Network”,
International Jo
urnal of
Electr
ical and Computer Engin
eering
(IJECE), Vol. 5, No. 2
,
April 2015, pp. 289~296.
[14]
J
.
Zhang
,
J
.
Li
,
X. F
a
n,
Z. D
e
ng,
“
R
es
earch
on
Re
al-T
im
e
Optim
al Path
Algorithm
of Urb
a
n Tr
ansport”
,
TELKOMNIKA Indonesian Journ
a
l
of Electrical
Engineering
, Vol.12, No.5
, May
2014, pp
. 3515
~ 3520.
BIOGRAP
HI
ES OF
AUTH
ORS
Dr.
Nabil Arman
is
a Com
puter S
c
ien
ce pro
f
es
s
o
r at P
a
l
e
s
t
i
n
e P
o
l
y
te
chnic
Univers
i
t
y
. H
e
received his BS
in Computer Scien
ce with
hig
h
honors from
Yarmouk University
, Jordan in
1990 and
an MS in Computer
Science from Th
e
Am
erican University
of Washing
t
on, DC USA
in 1997, and his Ph
D fro
m the School of Info
rm
ation Techno
log
y
and Engin
e
ering, George
Mason University
, Virgin
ia, USA in 2000. At Pales
tine Poly
tech
nic Univ
ersity
, h
e
worked
as th
e
MS Informatics Program Coor
dinator
and the h
ead of th
e Departm
e
nt of M
a
them
at
ics
and
Computer Scien
ce. Curr
ently
,
h
e
is the Dean o
f
the Colleg
e
of
Information Technolog
y
and
Computer Engineering
.
Dr. Arman is interest
ed in Database
and Knowledge-Base S
y
stems,
Algorithms, and Automated Software Engin
eerin
g.
He has published more than thirty
refereed
conferen
ce and
journal p
a
pers.
Dr. Faisal Khamay
seh
is
a Com
puter S
c
ien
ce as
s
i
s
t
ant pro
f
es
s
o
r. He recei
ved his
BS
in
Computer Information – Advan
ced Computer C
a
reers
,
from Southern Illinois U
n
iversity
, USA
1992, and MS i
n
Computer Science from same
university
in 1995, and his Ph
D in Computers
and Inform
ation
Sy
st
em
s from the Colleg
e
of Com
puters and Inform
ation, Helw
an Universit
y
,
Eg
y
p
t, in 2009
.Currently
working at Palestine
Poly
technic University
as instru
ctor and head of
Dept.
of Information Technolog
y
and
as instructor
of MS in Inf
o
rmatics. Dr
. Khamay
seh
is a
research
er in so
ftware eng
i
neering research
unit at
college of
Info
rmation Technolog
y
and
Com
puter Engineering
.
He is interested in
Computer Algorithms, Software Engin
eering and E-
learn
i
ng.
Evaluation Warning : The document was created with Spire.PDF for Python.