TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.5, May 2014, pp
. 3476 ~ 34
8
2
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i5.3236
3476
Re
cei
v
ed Ma
y 22, 201
3; Revi
sed
De
ce
m
ber 9, 2013
; Accepte
d
Decem
b
e
r
29, 2013
Shortest Path Analysis Based on Dijkstra's A
l
gorithm in
Emergency Response System
Ni Kai*,
Zha
ng Yao-tin
g
, Ma Yue-p
e
n
g
Shan
gh
ai Institute of W
o
rk Safet
y
Scie
nce, Shan
gh
ai ,200
2
33, Chi
n
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:
sno
w
mov
e
@
163.com
*
, zha
n
g
y
t@sh
aks.com.cn, ma
yp@
s
haks.com.cn
A
b
st
r
a
ct
In e
m
er
gency
situatio
ns, fin
d
i
ng s
u
ita
b
le
rou
t
es to
re
ach
de
stinatio
n is
criti
c
al iss
ue. T
h
e
shortes
t
path
pro
b
le
m i
s
on
e
of the
w
e
ll-kn
ow
n a
n
d
practica
l
pr
ob
l
e
ms
i
n
co
mput
er sci
ence,
net
w
o
rking
an
d ot
her
areas. T
h
is p
a
per pres
ents a
n
overvi
ew
on
shorte
st path
ana
lysis for an
effective e
m
e
r
gency res
p
o
n
s
e
mec
h
a
n
is
m to
mi
ni
mi
z
e
h
a
z
a
r
dous
eve
n
ts. Both gra
ph th
eo
ry and
netw
o
rk
ana
lysis i
n
GIS w
a
s discuss
e
d
for the purp
o
se
of mod
e
li
ng a
nd an
aly
z
i
n
g tr
affic netw
o
rks.
A transportatio
n
netw
o
rk can be referre
d to a
s
a val
ued
gra
p
h
consisti
ng of
a
set of vertices
and
a set of
e
d
ges. In ord
e
r to
compute
len
g
t
h
of the sh
orte
st
path fro
m
th
e
source to
eac
h of the r
e
mai
n
in
g in
t
he
gr
aph, w
e
i
llustr
a
ted D
ijkstra'
s
alg
o
rith
m
and
its
progr
a
m
. Based on the i
n
tegratio
n
of Geogra
phic In
formati
on Sys
t
em (GIS),
web servic
es an
d
Asynchro
no
us JavaScri
pt and
XML (Ajax) te
chno
log
i
es, w
e
provid
ed
a w
eb ap
plic
atio
n for findi
ng
opti
m
a
l
routes from l
o
c
a
tions of spec
i
a
li
z
e
d
resp
ons
e tea
m
station
s
to incide
nts site so as to ma
ximi
z
e
their a
b
i
lity
to respon
d to h
a
z
a
rd i
n
cid
ents
.
Ke
y
w
ords
:
sh
ortest path an
a
l
ysis, emerg
e
n
cy
respons
e, GIS, Dijkstra's algorith
m
Co
p
y
rig
h
t
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
The eme
r
ge
n
c
y re
spon
se
system in pu
blic eme
r
g
e
n
c
ie
s is the system by a serie
s
of
posed
action
that pe
ople
s
h
a
ve ta
ke
n after th
e p
ublic eme
r
ge
ncie
s
occu
rred,and
the
mai
n
purp
o
se i
s
to
re
duce th
e
degree
of da
mage
s in
du
ced by
publi
c
eme
r
ge
nci
e
s,to p
r
event
the
event's d
e
riv
a
tion or fu
rth
e
r expa
nsi
o
n
[1]. All su
ch
situation
s
mi
ght be carrie
d out from fires,
explos
ions
,traffic
acc
i
dent,terroris
m
,and natural
disas
t
ers
.
Univers
a
l
purpos
e
of any dis
a
s
t
er
manag
eme
n
t system i
s
to
deliver e
m
erg
ency
servi
c
e
s
su
ch a
s
poli
c
e, fire b
r
ig
a
de an
d medi
cal
servi
c
e as qu
ickly
a
s
p
o
ssi
b
le
in affe
cte
d
[2]. Duri
ng
an em
erg
e
n
cy it is very e
s
sential to
hav
e
accurate data
and take pro
m
pt action
s.
An e
ffective emergen
cy resp
on
se me
chani
sm might
be
possibl
e to minimize
and
control h
a
zard
ous eve
n
ts
b
y
prepa
ring fo
r su
ch eve
n
ts prior to
su
ch
an
occurre
n
ce,a
nd by a rapid
respon
se afte
rwa
r
d
s
.
In ca
se
of a
n
y
incid
ent, th
e em
erg
e
n
c
y
respon
se
officer n
eed
s
a
smart d
e
ci
sio
n
su
ppo
rt
system to re
ach the in
cid
ent locatio
n
as s
oon a
s
possibl
e [3].
There is a n
eed for faste
s
t
possibl
e re
spon
se both i
n
terms of d
i
spat
chin
g
the emerg
e
n
c
y services to
the location
o
f
disa
ster a
s
well as evacua
tion of the populatio
n fr
o
m
that location. This requ
ires h
a
ving p
a
th
analysi
s
that
woul
d en
able
the ro
uting
a
nd re-routin
g
of vehicle
s
from the va
rio
u
s
key lo
cati
ons
inclu
d
ing ho
spitals, fire an
d police depa
rtments
to th
e event scen
e and from th
e event scen
e to
shelte
rs, ho
spitals, or othe
r locatio
n
s.
Geog
rap
h
ic Informatio
n S
y
stems (GIS) wa
s
de
sign
ed to
su
ppo
rt geog
rap
h
ical inq
u
iry
and, ultimatel
y
, spatial
de
cisi
on m
a
ki
n
g
[4]. The va
lue of
GIS in
eme
r
ge
ncy
respon
se
a
r
i
s
e
s
dire
ctly from the benefits of integratin
g a te
chnol
o
g
y design
e
d
to suppo
rt spatial de
ci
si
on
makin
g
into
a field
with a
stro
ng
nee
d
to ad
dre
s
s n
u
merou
s
criti
c
al
sp
atial de
cisi
on
s. Fo
r t
h
is
rea
s
on, n
e
w
appli
c
ation
s
of GIS in em
erge
ncy m
a
n
ageme
n
t hav
e flouri
s
he
d i
n
re
cent ye
a
r
s
along
with an
interest in furthering thi
s
trend.
In emergen
cy manage
me
nt, there a
r
e
many su
bje
c
ts which have
to coo
perate
durin
g
solutio
n
of
crisis
situatio
n.GIS hold
s
th
e capab
ility t
o
integ
r
ate
maps with
d
e
tailed d
a
tab
a
se
informatio
n a
nd ima
g
e
s
, a
nd turns
ordi
nary ma
ps int
o
sm
art m
a
p
s
that
re
spon
d to qu
erie
s
and
helps in com
p
lex analysis
[5]. With its
ability to
relate geographi
cal
and
attribute data, GIS
can
be an
effectiv
e and
efficien
t platform for
the man
age
ment of info
rmation. GIS
provide
s
a m
ean
s
of rapid data
acce
ss a
nd q
uery ba
sed o
n
both geo
graphi
c location
and attribute
data.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Shorte
st Path Analysi
s Ba
sed on Dij
k
stra
's Algor
ithm
in Em
ergency Respon
se S
ystem
(Ni Kai
)
3477
Re
cently, mu
ch
wo
rk was
carrie
d out i
n
the
ap
plication of exiting
studie
s
fo
r e
m
erg
e
n
c
y
respon
se
systems co
nsi
d
e
r
ing
shorte
st path
a
nal
ysi
s
.Ming-Hsi
Hsu, et al. [6]
d
e
velope
d a
G
I
S
based de
ci
si
on su
ppo
rt sy
stem to enh
a
n
ce the
eme
r
gen
cy ope
rations d
u
ri
ng typhoo
n attacks in
Taiwa
n
; M.H.
Xu, et al. [7] make
so
me
cha
nge
s in th
e origi
nal
Dijkstra'
s
al
gorith
m
and o
b
tain
a
new imp
r
ove
d
Dij
k
stra'
s
shorte
st path
algorit
h
m
; O
ded Be
rma
n
, et al. [8] p
r
ese
n
ted
a n
o
vel
methodol
ogy
to dete
r
mine
the optim
al d
e
sig
n
of
a
sp
eciali
ze
d tea
m
net
work so
as to
maximi
ze
its ability to resp
ond to
su
ch in
cid
ents i
n
a regi
o
n
. Rui Ch
en, et al
. [9] develope
d a
set of de
sig
n
prin
ciple
s
tha
t
are g
r
o
und
e
d
in em
ergen
cy man
agem
ent co
ncepts
and al
so
in th
e insi
ghts fro
m
the real respo
n
se ma
nag
ers in the We
st
ern New Yo
rk area.
2. Graph The
or
y
and Netw
o
r
k Analy
s
is
There are cl
a
ssi
cal
pro
b
le
ms p
r
e
s
ente
d
as g
r
ap
hs such as sho
r
te
st
path,
lon
g
e
s
t
path,
travelling
sal
e
sma
n
p
r
obl
em. Fro
m
th
e view
of a
n
eme
r
ge
ncy
re
spo
n
se system, it is
an
importa
nt issue to redu
ce
the transmi
ssion ti
me through the net
work by anal
yzing the sp
atial
netwo
rk with
sea
r
ch p
r
o
c
e
dure. Fi
ndin
g
the shor
te
st
path fro
m
re
scue
sites to
accide
nt poi
nt
throug
h a
roa
d
network is
cru
c
ial fo
r e
m
erg
e
n
c
y se
rvice
s
.In orde
r to take
pro
m
pt action
s o
n
a
seri
ou
s accid
ent, it is important to con
s
truct an ap
pro
p
r
iate tran
sp
ortation netwo
rk.
The g
r
a
ph t
heory i
s
use
d
inten
s
ively
in o
peration
s
resea
r
ch,
discrete
mat
hematics,
combi
nato
r
ial
optimization
and net
work
analysi
s
[
10]. Graph
s p
r
ovi
ded a po
we
rful tool to model
obje
c
ts an
d relation
ship
s
among
obje
c
t
s
. Gra
p
h
s
are defined
by a set of verti
c
e
s
and
a se
t of
edge
s,
whe
r
e
ea
ch
edg
e
conne
cts two
of its ve
rtic
e
s
. Gra
p
h
s
a
r
e
further cl
assif
i
ed into
di
re
cted
and
undi
re
cted g
r
ap
hs,
d
epen
ding
on
wheth
e
r th
e
edge
s
are
di
rected
[11]. A
graph
struct
ure
can be exte
nded by assi
gning a wei
g
ht to eac
h edge of the graph. G
r
aph
s with weight
s,
or
wei
ghted
g
r
aph
s, a
r
e u
s
ed to represe
n
t stru
ct
ures i
n
whi
c
h
pai
rwise conn
ecti
ons
have
so
me
nume
r
ical values. For ex
ample if a grap
h
rep
r
e
s
ents a roa
d
network, the weight
s could
rep
r
e
s
ent the
length of each road [12].
A network is referred to as a pu
re n
e
twor
k if onl
y its topology and conn
e
c
tivity are
con
s
id
ere
d
. If a netwo
rk i
s
cha
r
acte
ri
zed by it
s to
pology a
nd f
l
ow
cha
r
a
c
te
ristics
(such
as
cap
a
cit
y
con
s
t
r
aint
s,
p
a
t
h
ch
oic
e
and
l
i
nk
co
st
fu
nct
i
ons) it i
s
ref
e
rred to
a
s
a
flow net
work. A
transpo
rtation
netwo
rk i
s
a flow netwo
rk rep
r
e
s
enti
ng the move
ment of peo
ple, vehicle
s
or
good
s [13]. The app
roa
c
h
adopte
d
almo
st universally
is to rep
r
e
s
en
t a transp
o
rta
t
ion netwo
rk
by
a set
of nod
e
s
an
d a
set of
links. A tran
sportation
net
work
ca
n be
referred to a
s
a valued
grap
h,
or alternativel
y a network.
Dire
cted lin
ks are referr
ed t
o
as a
r
cs, whi
l
e undirecte
d
links as e
dge
s.
The rel
a
tion
ship between t
he nod
es an
d the arcs
, re
ferre
d to as the network topolo
g
y, can
be
spe
c
ified by
a node
-a
rc i
n
cid
e
n
c
e ma
trix: A
tabl
e of binary or
terna
r
y varia
b
les
stating the
pre
s
en
ce or absen
ce
of a
relatio
n
shi
p
bet
ween n
e
twork el
em
ents. The
no
de-a
r
c in
cide
nce
matrix spe
c
ifi
e
s the net
work topolo
g
y an
d is useful for network p
r
o
c
essing.
A gra
ph
G
co
nsi
s
ts
of a
se
t V of vertice
s
a
nd
a set E
of ed
ge
s
su
ch th
at ea
ch
edge
in
E joins a pai
r of vertice
s
in V.
Graph
s ca
n
be finite and infinite, whe
n
V
and E
are finite
then
G
is
als
o
finite.
Grap
h
,
(1)
Whe
r
e:
Set of vertices
,
,
,
⋯⋯
for n v
e
rtic
es.
Set of edge
s
,
,
,⋯⋯
for m e
dge
s with
weights
w
su
ch that:
,
,
,⋯⋯
, where
.
Adjace
nt vertice
s
are a pai
r of vertice
s
jo
ined by a si
ngle edg
e an
d the two vertices in
this case a
r
e
incid
ent to th
e sa
me e
dge.
Adjacent ed
ges
are two
o
r
mo
re e
dge
s having
a si
n
g
le
comm
on vert
ex.
Figure 1
(
a) sho
w
s
a graph G
(V, E),
whe
r
e V(G)
= {v1, v2, v3,v4, v5}, and
E(G)
= {e1, e2, e3,
e4, e5, e6}. Order of
G = |
V| = 5 and Size of G = |E| = 6.
Network an
al
ysis
ha
s ma
n
y
practi
cal a
pplic
ation
s
, for exampl
e, to model a
n
d
analyze
traffic net
works. A traffi
c
netwo
rk
re
prese
n
ted by
a
dire
cted g
r
a
ph con
s
istin
g
of a finite set of
node
s
and
a
finite set
of p
a
th which i
s
conne
cted
to e
a
ch
othe
r. Ea
ch
path i
n
the
traffic
network
has an a
s
so
ciated gene
rali
zed cost which could b
e
a
combi
nation
of travel time, direct co
st a
nd
travel distan
ce. A path betwee
n
two no
des i
s
an alt
e
rnatin
g se
q
uen
ce of vertice
s
and e
d
g
e
s
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3476 – 34
82
3478
starting
and
e
nding
with th
e vertice
s
. Th
e length
of
a
path is th
e su
m of the weig
hts of the e
d
g
e
s
on the path.
The
sho
r
te
st path
is a
cla
ssi
cal
an
d
main
proble
m
in n
e
two
r
k a
nalysi
s
a
nd it i
s
mandato
r
y for GIS. It has multiple
re
alizatio
ns a
n
d
is hig
h
ly depe
ndent o
n
the nature
of
transpo
rtation
netwo
rk an
d
the di
st
an
ce
betwe
en
ori
g
in an
d d
e
sti
nat
ion. As m
ention in
(1
),
the
co
st of sho
r
test path fro
m
vertex u to vertex v is
)
,
(
v
u
dist
,
such t
hat
v
u
w
v
u
dist
)
,
(
is
minimum. Fig
u
re
1(b
)
sho
w
s th
e sho
r
test path fo
r g
r
aph
G a
s
d
e
f
ined in
(1) f
r
om vertex v3
to
vertex v5 with a cost of 9.
1
2
5
3
4
1
5
4
3
2
6
(a) Typi
cal g
r
aph
(b) G
r
a
ph of sho
r
test path
with wei
ghts
Figure 1. Typical G
r
aph a
n
d
a Gra
ph Ed
ges
with Wei
ghts
GIS are de
si
gned to
capt
ure, an
alyze,
repres
ent spatial data in
a way that use
r
can
easily u
nde
rstand. The
gra
phs i
n
GIS a
r
e geo
graphi
cally referen
c
e
d
, and
ea
ch v
e
rtex ha
s a
well
defined
ab
sol
u
te coordinat
es
relate
d to
earth.
Network a
nalysi
s
problem
s a
r
e
m
odele
d
a
s
g
r
a
p
h
probl
em
s based on the un
derlying g
r
ap
h model
of
n
e
tworks.
Since there can b
e
more than
one
path bet
ween
two vertices,
there i
s
then
the pr
o
b
lem
of finding a
path with the
minimum
co
st
betwe
en the
s
e two
spe
c
i
f
ied vertices.
The o
p
tima
l
path in traffi
c net
wo
rks
is an
optimi
z
ati
on
probl
em that finds the o
p
timal minimum
value path a
m
ong ma
ny alternatives.
3. Dijkstra
's
Algorithm a
nd its Progr
am
3.1. Dijkstra
's Algorithm
Dijkstra
's
alg
o
rithm i
s
call
ed the
singl
e
-
so
ur
ce
sh
ort
e
st path
and
is refe
rred t
o
as th
e
stand
ard
sho
r
test p
a
th al
g
o
rithm
s
. It co
mputes le
n
g
th of the
sh
ortest path
fro
m
the
sou
r
ce
to
each of the remainin
g vert
ice
s
in the g
r
aph. Dij
kst
ra'
s
algo
rithm
solves the p
r
o
b
lem of findi
ng
the sho
r
test
path from a
point in
a gra
ph (the so
urce)
to
a de
stin
ation. It ca
n
also
be
u
s
ed
for
finding co
sts
of shorte
st pa
ths from a sin
g
le vert
ex to a single d
e
sti
nati
on vertex by stopping t
he
algorith
m
on
ce the sho
r
test
path to the destinatio
n vertex has bee
n determi
ned [1
4].
The i
nput
of the al
gorith
m
con
s
i
s
ts of
a
weig
hted dire
cted graph
)
,
,
(
w
E
V
G
and
a
s
o
ur
ce ver
t
ex
s
in
G
. We
will
denote
V
the set of all vertices in
the g
r
ap
h
G
. Each
edg
e of the
grap
h is an o
r
de
red p
a
ir of
vertices
)
,
(
v
u
rep
r
ese
n
ting a co
nne
ction from
vertex
u
to ve
rtex
v
.
The set of all edge
s i
s
denote
d
E
. Weig
hts of
edge
s a
r
e g
i
ven by a weight fun
c
tio
n
]
,
0
[
:
E
w
; therefore
)
,
(
v
u
w
is the non-n
e
g
a
tive cost of moving from
vertex
u
to ver
t
ex
v
. The co
st of an edg
e can
be thoug
ht of as (a
gen
era
lization of
) th
e distan
ce
be
tween tho
s
e
two ve
rtice
s
.
The
co
st of
a
path
betwee
n
two
verti
c
e
s
i
s
the
sum
of co
sts of th
e ed
ge
s in
th
at
path.
A path between two no
d
e
s
0
v
and
k
v
is finite sequ
en
ce
k
v
v
v
v
p
....
2
1
0
of nodes
su
ch th
at for
each
E
v
v
k
i
i
i
1
,
0
, and the
wei
ght of the
path i
s
)
(
)
(
1
0
i
i
k
i
v
v
w
p
w
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Shorte
st Path Analysi
s Ba
sed on Dij
k
stra
's Algor
ithm
in Em
ergency Respon
se S
ystem
(Ni Kai
)
3479
The shorte
st
path wei
ght, also
calle
d di
stan
ce, from
node
u
to
v
, denoted
)
,
(
v
u
dist
, is
the
minimum wei
ght of all possible di
re
cted
paths with o
r
igin
u
and de
st
ination
v
.
Let
v
u
p
den
otes t
hat
v
is
rea
c
h
able from
u
throug
h the
directed
path
p
. We
have formul
a:
}
:
)
(
min{
)
,
(
v
u
p
w
v
u
dist
p
(2)
For a source
node
V
s
, the sh
ortest path al
gorithm
cal
c
u
l
ates the di
stance
)
,
(
v
s
dist
for all
V
v
. Suppose that
S
is a prop
er
sub
s
et of
V
such that
S
s
, and let
S
denote
S
V
. If
v
u
s
p
...
is
a sho
r
test path
from
s
to
S
then clea
rly
S
u
and th
e
)
,
(
u
s
-
s
ec
tion
of path
p
must be a sh
orte
st path from
s
to
u
.
Therefore th
e
distan
ce fro
m
s
to
S
is give
n by
the formula:
)}
(
)
,
(
{
min
)
,
(
,
uv
w
u
s
dist
S
s
dist
S
v
S
u
(
3
)
This fo
rmula
is the ba
si
s
of sho
r
test p
a
th algo
rithm
.
Staring with
the set
}
{
0
s
S
, an
increa
sing se
quen
ce
1
1
0
,.....
,
n
S
S
S
of su
bset of
V
is co
nstru
c
ted, in
su
ch a
way t
hat, at the
end of stag
e
i
,
s
h
ortes
t
paths
from
s
to all
node
s in
i
S
are kno
w
n.
3.2. Descrip
tion of the
Algorithm
Dijkstra
's alg
o
rithm
wo
rks by ke
epin
g
f
o
r e
a
ch vert
ex
v
the
co
st
d[v] of the shorte
st
path foun
d
so
far bet
wee
n
s
and
v
. Initially,
this
value is
0 for the sourc
e
vertex s
(d[s
]=
0), and
infinity for all
other verti
c
e
s
, repre
s
e
n
ting
the fa
ct that
we do n
o
t kn
ow any path l
eadin
g
to those
vertice
s
. Th
e
followin
g
p
s
eudo
-code
gi
ves a
brief
d
e
scriptio
n of
the wo
rk
ing
of the Dji
k
stra's
algorith
m
.
Procedur
e
Dijs
k
t
ra (V: s
e
t
of v
e
rtic
es
1... n {Vertex
1 is
the s
o
urc
e
}
Adj[1…n] of adjacen
cy li
sts;
EdgeCost
(
u, w): edg
e-co
st
function
s;)
Var
: sDi
s
t[1…n] of path costs from
sou
r
ce
(ver
te
x 1); {sDi
st[j] will be equ
al to the length
of the sho
r
test path to j}
Begin
:
Initializ
e
{Create a vi
rt
ual set Fronti
e
r to store i
where
sDi
s
t[i] is alre
ad
y fully solved}
Cre
a
te em
pty Priority Q
ueu
e Ne
w Fro
n
tier;
s
D
is
t[1]
0; {
T
he dista
n
ce to the sou
r
ce
is ze
ro}
forall
vertices w in V-{1}
do
{no edg
es
have bee
n explore
d
yet}
s
D
is
t[w]
end for
;
Fill New F
r
ontier with vertices w in
V organized by pri
o
rities
sDi
s
t[w];
end
Initialize;
repea
t
v
Delete
Min
{
Ne
w Frontier}; {v is the ne
w
c
l
os
es
t; s
D
is
t[v
] is
already
c
o
rrec
t}
forall
of the neighb
ors w in
Adj[v]
do
if
s
D
is
t[w]>sDis
t[v
] +
E
dgeCos
t
(v
,
w
) then
s
D
is
t[w]
s
D
is
t[v
] +
E
dgeCos
t(v
,
w)
update
w in New Frontier {
w
ith ne
w prio
rity sDist[
w]}
end
if
end
for
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3476 – 34
82
3480
until
Ne
w Frontier is em
pt
y
end
Dij
k
stra;
When the algorithm finishes, d[v] will be the co
st of the shortest pa
th from s to v -- or
infinity, if no su
ch p
a
th exi
s
ts. Th
e ba
si
c op
eratio
n o
f
Dijkstra'
s
al
gorithm i
s
e
d
ge rel
a
xation:
if
there i
s
a
n
e
dge from u to
v, then the shorte
st
kno
w
n path from
s to u (d[u]) ca
n be exten
d
e
d
to
a path from s to v by adding edge
(u,v) at the end.
This path
will h
a
ve length d[
u]+w(u,v). If this
is less than th
e curre
n
t d[v], we ca
n repl
a
c
e t
he current
value of d[v]
with the ne
w value.
Edge rel
a
xation is ap
plied
until all values d[v]
rep
r
e
s
ent the
co
st of the sho
r
test pat
h
from
s to v. T
he alg
o
rithm
i
s
o
r
ga
nized
so that
ea
ch
e
dge
(u,v) i
s
relaxed o
n
ly o
n
ce,
whe
n
d[
u]
has rea
c
he
d its final value. Dijkstra'
s
Algorithm
solve
s
the singl
e-source
shorte
st path proble
m
in weig
hted
grap
hs. As
a
simple a
nd
con
s
e
que
ntly easily imple
m
ented
al
gorithm, Dijkstra
's
algorith
m
de
p
end
s on
the
data st
ru
ctures u
s
e
d
to im
plement th
e
grap
h rep
r
e
s
enting the
sp
atial
netwo
rk.
4. A Cas
e
of
Emergenc
y
Resp
onse S
y
stem
GIS is a po
werful to
ol in
the analysi
s
and
de
sig
n
of transport
routing net
wo
rks. Its
graphical di
splay capabilit
ies allow not only visual
i
z
ation of the
different rout
es but also t
h
e
seq
uen
ce in
whi
c
h they are built, which
allows
the u
nderstan
ding
of the
logic b
ehind the ro
u
t
ing
netwo
rk de
si
gn [15]. A
GIS analysi
s
i
n
eme
r
ge
ncy respon
se
is based on a spatial
data
b
a
se
whi
c
h in
clu
d
e
s
be
sid
e
othe
r data
also g
eocode
d ad
d
r
esse
s. Th
e
spatial
datab
ase i
n
cl
ude
s
the
traffic netwo
rks, admini
s
t
r
ative divisio
n
s, ha
za
rdo
u
s site
s, ho
spital lo
catio
n
s, pop
ulati
on
distrib
u
tion, major p
ublic f
a
cilitie
s, etc.
Whe
n
an accident wa
s ha
ppen
ed,eme
r
gen
cy manag
ers
can
ea
sily o
b
t
ain the
re
qui
red
informati
on o
n
th
e h
a
z
ard
scen
ario
s, find
availa
ble
re
sou
r
ces in
the neighb
o
u
rho
od, and
evaluate the appli
c
abl
e
resp
on
se
measures vi
a the emerg
ency
respon
se
system for maki
n
g
deci
s
io
ns.
A Web
servi
c
e i
s
a software sy
stem
desig
ned to
sup
port inte
rope
ra
ble ma
chin
e-to
-
machi
ne inte
raction ove
r
a
netwo
rk.
We
b se
rvice
s
p
r
ovides a
stan
dard m
ean
s
of interop
e
rat
i
ng
betwe
en diff
erent
software appli
c
atio
n
s
, ru
nnin
g
o
n
a vari
ety of platform
s [16]. GIS Web
Service
s
Se
rvices are di
scoverabl
e, self-de
s
cr
ibi
ng
software
comp
onent
s for m
a
kin
g
a
re
ality of
cre
a
ting a pl
atform inde
p
ende
nt distrib
u
tion ch
ann
el
for GIS data. Application
s
can
sha
r
e d
a
ta
from different
data sou
r
ces and format
s and have the
m
combi
ned i
n
a singl
e ap
plicatio
n.
Based o
n
GIS web se
rvices, we d
e
vel
oped a em
ergen
cy respo
n
se
web a
p
p
lication
whi
c
h was scripted in C#.NET, ASP.NET, JavaSc
ri
pt and HTM
L
code. Microsoft Visual Studio
w
a
s
th
e pr
og
r
a
mmin
g
co
mp
iler
s
o
ftw
a
r
e
.
Arc
G
IS
Server a
n
d
ArcGIS S
e
rver Appli
c
ation
Develo
per F
r
amework (A
DF) runtim
e
were install
e
d for the dist
ribution of th
e web ap
plication
.
The web b
r
o
w
ser b
a
sed clients could
communi
cate
with the web
GIS servi
c
e throu
gh the G
I
S
web
services.
The
cli
ents
perfo
rm
URL
re
que
st
s
to map se
rvice
and obtain
m
aps.
A
GIS Java
applet is u
s
e
r
interface that
can be u
s
ed
to retrieve an
d handle the
vector an
d ra
ster ma
p usin
g
the map tools
We u
s
e Aj
ax techn
o
logy t
o
acce
ss the
spat
ial
datab
ase. Ajax all
o
ws
we
b pa
ge
s to be
update
d
a
s
y
n
ch
ron
o
u
s
ly
by exch
angi
ng
small
am
ount
s of d
a
ta with
the
server be
hind
the
scene
s. This means that
it is
possible
to update p
a
rts of a we
b page, with
out reloa
d
ing
the
whol
e p
age [
17]. A traditio
nal
web
appli
c
ation
u
s
er’
s
action
trigg
e
rs
a
n
HTTP reque
st
to a we
b
serve
r
, whi
c
h
processe
s the req
u
e
s
t and retu
rn
s an HTML pa
g
e
to the clien
t. And additional
requ
est
s
lo
ck up the a
ppli
c
ation
until the sy
st
em u
pdate
s
the p
age. While A
j
ax appli
c
atio
n
s
cre
a
te
a
Jav
a
Scri
pt-ba
s
e
d
en
gine
that
ru
ns on
the
browse
r.
With Ajax, web
appli
c
ation
s
can
sen
d
d
a
ta to
, and
ret
r
iev
e
data
fro
m
, a
se
rver
a
synchrono
usly
(in
the
ba
ckgroun
d) wit
hout
interferi
ng wit
h
the displ
a
y and be
havior
of the existing page.
An integrated
emergen
cy resp
on
se
syst
em is a
de
cision suppo
rt system that su
pport
s
the emergen
cy mana
ger i
n
planni
ng, coordi
nat
ing,
and impl
eme
n
ting re
scue
and a
ssi
stan
ce
and oth
e
r
su
pport
ope
rati
ons
duri
ng t
he resp
on
se
pro
c
e
s
se
s. In our
eme
r
gen
cy re
spo
n
se
system,the wab appli
c
atio
n contain
s
to
ols to either
sele
ct the Start/End location dire
ctly on
the
map. Shorte
st path analysi
s
is u
s
e
d
to a
nalyze
the
sh
ortest
route b
e
twee
n users’ defined o
r
igi
n
and de
stinati
on on the server, and its resulta
n
t rout
e is ren
d
e
r
ed
on top of the map se
rvice in
grap
hical format using a
map co
ntrol
grap
hics
laye
r. Figure 2
shows the sh
ortest path in
the
emergen
cy resp
on
se sy
stem. Emerge
ncy man
age
rs can u
s
e t
he sh
orte
st
path functio
n
to
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Shorte
st Path Analysi
s Ba
sed on Dij
k
stra
's Algor
ithm
in Em
ergency Respon
se S
ystem
(Ni Kai
)
3481
sea
r
ch th
e
re
scue
ro
ute a
n
d
then
d
e
termine
qui
ckly
as to
whi
c
h
rescue
team
should
move
to the
accide
nt locat
i
on and
whi
c
h
path sho
u
ld
be followed.
The emergency response
web application will
display the accident location and relative
informatio
n on map so tha
t
emerge
ncy comm
and
ce
nt
er ca
n se
arch this info
rmation insta
n
t
ly.
The dynami
c
integration o
f
web mappi
ng se
rvice
s
a
nd inform
atio
n can p
r
ovid
e more a
c
curate
and effective
informatio
n for deci
s
io
n ma
king p
r
o
c
e
s
ses.
Figure 2. The
Shortest Pat
h
in Emerge
n
c
y Re
spo
n
se System
A well d
e
si
g
ned a
nd
co
mpre
hen
sive
databa
se
is the pri
m
e
requireme
nt for a
goo
d
netwo
rk a
nal
ysis. The
r
e a
r
e many extensio
ns
to the
basi
c
GIS data model ne
eded to su
pp
ort
sho
r
test
path
analysi
s
. We
defined th
e le
ngth of t
he
ro
ad to
cal
c
ulat
e the
sho
r
test
path fro
m
on
e
node to the target nod
e in a map, and then sele
ct
the optimal path a
m
ong the ro
a
d
base
d
on th
e
minimum
wei
ght. In our e
m
erg
e
n
c
y re
spon
se
syst
e
m
, the sho
r
te
st path a
nalysis
do not
co
nsid
er
other contrib
u
t
ing factor
s (road width, sp
eed limit, surf
ace
condi
tio
n
,
and turn re
striction
s
), whi
c
h
sho
u
ld be d
e
fined in the da
tabase to ide
n
tify more rea
listic ro
utes.
5. Conclusio
n
Whe
n
an a
ccident wa
s h
a
ppen
ed, findi
ng a path
wh
ich ta
kes
min
i
mum time to
rea
c
h
destin
a
tion is important fo
r rescu
e
. Find
ing sh
orte
st path is n
o
t a solutio
n
all th
e time becau
se
there a
r
e
sev
e
ral fa
ctors a
ffecting travel
time.
The paper
discu
ssed the shorte
st path an
alysis
based o
n
Di
jkst
ra’s alg
o
rithm and im
plemente
d
a
emergen
cy
respon
se
sy
stem b
a
sed
on
GIS,which ca
n be
widely
use
d
in all
sorts
of
se
rvices that i
n
an
y way ha
ndl
e so
urce
s a
n
d
con
s
e
que
nce
s
of em
erge
ncie
s. Curre
n
tly, the
appl
ication
provides the
optim
al ro
ute with
out
con
s
id
erin
g road conditio
n
s
and traffic con
g
e
s
tion.
F
u
rthe
r re
sea
r
ch is fo
cu
se
d on integrating
this sy
stem
with real time
on-roa
d
traffi
c
count to
di
splay m
o
re
d
y
namic, relia
ble an
d a
c
cu
rate
route
s
to eme
r
gen
cy man
a
gers.
Ackn
o
w
l
e
dg
ements
This resea
r
ch wa
s supp
orted by the
2013 Yea
r
Plan of Scie
nce a
nd Te
chnolo
g
y
Innovation Action of Shanghai (Gra
nt No. 1323
1
2
0180
0). It was also gra
n
t
from Shanghai
Institute of Work Safety Science.
Referen
ces
[1]
Hua
ng
Hon
g
ch
un, So
ng Y
i
n
g
hua.
Rese
arch
on t
he
Constr
uction
an
d Imp
r
oveme
n
t to th
e Emerg
enc
y
Resp
onse Mec
han
ism in Pu
bl
ic Emerge
ncie
s.
Informatio
n Engi
neer
in
g a
nd App
licati
o
n
s
. 2012; 15
4
:
458-
459.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3476 – 34
82
3482
[2]
Varsha
Mal
i
,
Madh
uri
Ra
o, et a
l
. AHP
Driv
en GIS
Base
d Em
er
genc
y
Ro
utin
g i
n
D
i
saste
r
Mana
geme
n
t.
Co
mmun
icati
o
ns in Co
mputer
and Infor
m
ati
o
n Scienc
e
. 201
3; 361: 23
7-24
8.
[3]
Granvill
e K
i
n
g
. Crisis
ma
na
ge
ment a
n
d
t
eam
effective
ness:
a cl
oser
e
x
am
i
natio
n.
Journal of B
u
siness
Ethics.
2002; 4
1
(3): 235-
24
9.
[4]
Goodch
ild
ME. Geogr
aph
ic i
n
formation
scie
n
c
e a
nd s
y
stem
s for e
n
viro
nm
ental
man
a
g
e
ment.
An
nu
al
Review
of Envi
ron
m
e
n
t and R
e
sourc
e
s
. 200
3; 28: 493-
519.
[5]
Dave W
r
az
ien,
Micha
e
l Y
oun
g. Overvie
w
of
Arc
GIS Solutio
n
s in S
e
rvic
e-
Oriented Arc
h
it
ectures. ESRI
Devel
o
p
e
r Su
mmit. 2006.
[6]
Ming-Hs
i Hsu,
Albert S Che
n
,
et al. A GIS-b
ased D
e
cisi
on
Supp
ort S
y
ste
m
for
T
y
p
h
o
o
n
Emergenc
y
Resp
onse i
n
T
a
i
w
a
n
.
Geotec
hnic
a
l an
d Geo
l
ogic
a
l En
gi
nee
ring.
20
11; 29:
7–1
2.
[7]
MH
Xu
a, YQ
Liu,
et a
l
. An
i
m
prove
d
D
ijkst
ra'
s
shortest
p
a
th a
l
g
o
rithm f
o
r sp
arse
net
w
o
rk.
App
lie
d
Mathe
m
atics a
nd Co
mputati
o
n
. 2007; 1
85: 2
47-2
54.
[8]
Oded Berma
n,
Vedat Verter, et al. Desig
n
i
n
g emerg
enc
y r
e
spo
n
se n
e
t
w
o
r
ks for hazard
o
u
s materia
l
s
transportati
on.
Co
mp
uters & Operatio
ns Re
search.
20
07;
34:13
74-
138
8.
[9]
Rui C
hen, R
a
j
Sharman, et
al. Desi
gn pr
in
ci
ples for critic
al inc
i
de
nt res
pons
e s
y
st
ems
. Inform
ation
Systems a
nd e
-
Busin
e
ss Man
age
ment
. 200
7
;
5: 201–2
27.
[10] Moham
ed A. Eleich
e.
Net
w
or
k
Anal
ysis Met
hods for Mo
bil
e
GIS. Un
iversit
y
of W
e
st Hu
ngrar
y. 20
11
;
9.
[11]
Samir Kh
ull
e
r,
Bala
ji R
a
g
hava
c
hariI. Graph
a
nd
N
e
t
w
ork A
l
gorithms. ACM
Comp
utin
g Su
rve
y
s.
199
6;
28(1): 43-
49.
[12] Graph
theor
y
.
http://en.
w
i
k
i
pedia.or
g
/
w
iki/Gr
aph_theor
y
[13]
MGH Bell, Yas
unor
i Iida. T
r
ansportatio
n
Net
w
o
r
k
Ana
l
ysis. Ne
w
York: Joh
n
W
ille
y & Son
s
Ltd. 1997.
[14]
Dijkstra's algorithm .http://en.
w
i
ki
p
e
d
i
a.org/
w
i
ki/Di
j
kstra'
s
_
a
lg
orithm
[15]
Gupta P, PK
S
i
k
dar, N
Ja
in
e, K
Kumar.
Ge
o
g
rap
h
ica
l
Infor
m
ati
o
n
Syste
m
in
T
r
ansp
o
rtati
on P
l
an
ni
ng
.
Procee
din
g
s of
Map Asia Co
n
f
erence. 20
03;
10: 13-1
5
.
[16]
W
eb Services
Architecture. ht
tp://
w
w
w
.
w
3
.
o
r
g
/T
R/
w
s
-arc
h/
[17]
AJAX
Introduction. http://
w
w
w.
w
3
sc
ho
ols.co
m/aja
x
/aj
a
x_i
n
tro.asp
Evaluation Warning : The document was created with Spire.PDF for Python.