
(
(ng i ng
ng i ng)
)n nh
n nh
t
t
Gii thiu:
Bài toán tìm ng i ngn nht là bài
toán quan tr ng trong lý thuyt  >/. $c 7ng
d8ng trong th?c t: Giao thông, vi&n thông…
Bài toán chia làm 2 loi:
Tìm (ng i ng)n nht gia 1 cp *nh: Cho 2
nh u,v thuc G, tìm ng i ngn nht t;n
v : Dkstra
Tìm (ng i ng)n nht gia tt ccác cp
*nh: Tìm ng i ngn nht tnh u n nh
v, vi m i c9p nh u,v thuc G: Floyd-Warshall
Gi
Gi
i thu
i thu
t Dijkstra
t Dijkstra
Gii thiu:
- Gii thut Dijkstra gii bài toán ng i ngn
nht ngun ơn (Single Source Shortest Path) trên
mt  thcó tr ng scnh +u không âm.
- Xác nh ng i ngn nht gia 2nh a,b23>c
t vn :
Dng d8ng gii thut cây bao trùm ti
thi%u % gii quyt bài toán ng i ngn nht có
$c không???
Gi
Gi
i thu
i thu
t D
t D
kstra
kstra
Nhn xét:
- Gii thut % gii bài toán MST skhông 7ng d8ng
$c cho bài toán ng i ngn nht.
-Vì sao??
- Vì vy cn phi chnh s:a gii thut trên % phù
h$p vi bài toán ng i ngn nht
Gi
Gi
i thu
i thu
t D
t D
kstra
kstra
Gii thut:
-Em!i nh v, gii thut Dijkstra xác nh 3 thông
tin: kv,dv,pv
•kv = 0 ho9c 1 – xác nh trng thái ca nh v ( 0 –
cha ch n, 1 –F2 n)
•dv: Chi+u dài ng i tìm thy ti thi i%m ang
xét tn v
•pv: là

nh tr

c c
a

nh v trên

ng
i ng
n nh
t t
a
G
.

ng
i ng
n nh
t t

n b có d
ng
{a,…,pv,v,…,b}
Gi
Gi
i thu
i thu
t D
t D
kstra
kstra
B1: Kh4i to: k
v
=0,∀v∈V; d
v
=
∞
,∀v ∈V \{a}; d
a
=0.
B2: Ch n v∈Vsao cho k
v
=0 và d
v
= min {d
t
/ t
∈
V,k
t
=0 }
–Nu d
v
= ∞thì kt thúc, không tn ti ng i tab.
B3: ánh du nh v, k
v
=1.
B4: Nu v=b thì kt thúc và d
b
là  dài ng i ngn
nht tab.
Ng$c li nu v
≠
bsang B5.
B5: Vi m!i nh uk+vi vmà k
u
= 0, ki%m tra
Nu d
u
> d
v
+ w(v,u) thì d
u
= d
v
+ w(v,u)
Ghi nhnh v: p
u
:= v. Quay li B2.