Các bài toán về đường đi trong đồ thị và các thuật toán

http://www.ebook.edu.vn

Chu

.o

.ng 3

C´ac b`ai to´an vˆe

`d¯u

.`o

.ng d¯i

Trong c´ac ´u

.ng du

.ng thu

.

.c tˆe

´, ta cˆa

`n t`ım d¯u

.`o

.ng d¯i (nˆe

´u c´o) gi˜u

.a hai d¯ı

˙’nh cu

˙’a d¯ˆo

`thi

.. D

-ˇa

.c

biˆe

.t, b`ai to´an t`ım d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t gi˜u

.a hai d¯ı

˙’nh cu

˙’a mˆo

.t d¯ˆo

`thi

.c´o ´y ngh˜ıa to l´o

.n. C´o

thˆe

˙’ dˆa

˜n vˆe

`b`ai to´an nhu

.vˆa

.y t`u

.nhiˆe

`u b`ai to´an thu

.

.c tˆe

´. V´ı du

., b`ai to´an t`ım h`anh tr`ınh

tiˆe

´t kiˆe

.m nhˆa

´t (theo tiˆeu chuˆa

˙’n khoa

˙’ng c´ach, th`o

.i gian hoˇa

.c chi ph´ı) trˆen mˆo

.t ba

˙’n d¯ˆo

`giao

thˆong; b`ai to´an cho

.n phu

.o.ng ph´ap tiˆe

´t kiˆe

.m nhˆa

´t d¯ˆe

˙’ d¯u

.a mˆo

.t hˆe

.d¯ˆo

.ng lu

.

.c t`u

.tra

.ng th´ai

n`ay sang tra

.ng th´ai kh´ac v.v... Hiˆe

.n nay c´o rˆa

´t nhiˆe

`u phu

.o.ng ph´ap du

.

.a trˆen l´y thuyˆe

´t d¯ˆo

`

thi

.to

˙’ ra l`a c´ac phu

.o.ng ph´ap c´o hiˆe

.u qua

˙’ nhˆa

´t.

Chu

.o.ng n`ay tr`ınh b`ay c´ac thuˆa

.t to´an t`ım d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t trˆen d¯ˆo

`thi

.c´o tro

.ng sˆo

´.

3.1 D

-u

.`o

.ng d¯i gi˜u

.a hai d¯ı

˙’nh

3.1.1 D

-u

.`o

.ng d¯i gi˜u

.a hai d¯ı

˙’nh

Trong nhiˆe

`u tru

.`o

.ng ho.

.p, ch´ung ta cˆa

`n tra

˙’ l`o

.i cˆau ho

˙’i: Tˆo

`n ta

.i d¯u

.`o

.ng d¯i µt`u

.d¯ı

˙’nh sd¯ˆe

´n

d¯ı

˙’nh tcu

˙’a d¯ˆo

`thi

.c´o hu

.´o

.ng G:= (V, E)? Nˆe

´u c´o, h˜ay chı

˙’ ra c´ach d¯i cu

˙’a d¯u

.`o

.ng d¯i µ.

L`o

.i gia

˙’i cu

˙’a b`ai to´an n`ay kh´a d¯o

.n gia

˙’n: ch´ung ta chı

˙’ cˆa

`n ´ap du

.ng thuˆa

.t to´an t`ım kiˆe

´m

theo chiˆe

`u rˆo

.ng (hoˇa

.c chiˆe

`u sˆau) trˆen d¯ˆo

`thi

.c´o hu

.´o

.ng Gnhu

.sau. G´an mˆo

˜i d¯ı

˙’nh cu

˙’aGmˆo

.t

chı

˙’ sˆo

´. Bˇa

`ng phu

.o.ng ph´ap lˇa

.p, dˆa

`n dˆa

`n ta s˜e cho mˆo

˜i d¯ı

˙’nh vmˆo

.t chı

˙’ sˆo

´n`ao d¯´o bˇa

`ng d¯ˆo

.

d`ai d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t (sˆo

´cung ´ıt nhˆa

´t) t`u

.st´o

.iv. D

-´anh dˆa

´u d¯ı

˙’nh sbˇa

`ng chı

˙’ sˆo

´0. Nˆe

´u

c´ac d¯ı

˙’nh d¯u

.o.

.c d¯´anh dˆa

´u bˇa

`ng chı

˙’ sˆo

´mlˆa

.p th`anh mˆo

.t tˆa

.p ho.

.pP(m) d¯˜a biˆe

´t, th`ı ta d¯´anh

dˆa

´u chı

˙’ sˆo

´(m+ 1) cho mo

.i d¯ı

˙’nh cu

˙’a tˆa

.p ho.

.p:

P(m+ 1) := {vjchu

.a d¯u

.o.

.c d¯´anh dˆa

´u|tˆo

`n ta

.ivi∈P(m) v´o

.i (vi, vj)∈E}.

75

http://www.ebook.edu.vn

Thuˆa

.t to´an d`u

.ng khi khˆong thˆe

˙’ d¯´anh dˆa

´u d¯u

.o.

.c n˜u

.a. C´o hai tru

.`o

.ng ho.

.p xa

˙’y ra:

1. D

-ı

˙’nh td¯u

.o.

.c d¯´anh dˆa

´u, chˇa

˙’ng ha

.nt∈P(m) v´o

.imn`ao d¯´o, th`ı ta x´et c´ac d¯ı

˙’nh v1, v2, ...,

sao cho

v1∈P(m−1), v2∈P(m−2), . . . , vm∈P(0).

Khi d¯´o µ:= {s=vm, vm−1, ..., v1, t}l`a d¯u

.`o

.ng d¯i pha

˙’i t`ım.

2. D

-ı

˙’nh tkhˆong d¯u

.o.

.c d¯´anh dˆa

´u. Trong tru

.`o

.ng ho.

.p n`ay, ta kˆe

´t luˆa

.n khˆong tˆo

`n ta

.i d¯u

.`o

.ng

d¯i t`u

.sd¯ˆe

´nt.

Theo c´ach xˆay du

.

.ng cu

˙’a thuˆa

.t to´an, dˆe

˜d`ang ch´u

.ng minh rˇa

`ng

Mˆe

.nh d¯ˆe

`3.1.1 Nˆe

´u d¯ˆo

`thi

.d¯u

.o.

.c x´ac d¯i

.nh bo.

˙’ i d˜ay liˆen tiˆe

´p c´ac d¯ı

˙’nh, th`ı thuˆa

.t to´an c´o

th`o.i gian O(m).

3.1.2 D

-ˆo

`thi

.liˆen thˆong ma

.nh

Nhˇa

´c la

.i l`a d¯ˆo

`thi

.c´o hu

.´o

.ng Ggo

.i l`a liˆen thˆong ma

.nh nˆe

´u hai d¯ı

˙’nh sv`a tt`uy ´y cu

˙’aGluˆon

luˆon tˆo

`n ta

.i mˆo

.t d¯u

.`o

.ng d¯i t`u

.sd¯ˆe

´nt. Hiˆe

˙’n nhiˆen rˇa

`ng

D

-i

.nh l´y 3.1.2 Cho G= (V, E)l`a d¯ˆo

`thi

.c´o hu

.´o.ng, v`a v∈V. Khi d¯´o Gliˆen thˆong ma

.nh

nˆe

´u v`a chı

˙’ nˆe

´u mo

.i cˇa

.p d¯ı

˙’nh a, b ∈V, tˆo

`n ta

.i mˆo

.t d¯u

.`o.ng d¯i t`u

.ad¯ˆe

´nvv`a mˆo

.t d¯u

.`o.ng d¯i t`u

.

vd¯ˆe

´nb.

Du

.

.a trˆen thuˆa

.t to´an t`ım kiˆe

´m theo chiˆe

`u sˆau, ta c´o thˆe

˙’ mˆo ta

˙’ c´ach x´ac d¯i

.nh mˆo

.t d¯ˆo

`

thi

.c´o hu

.´o

.ng c´o liˆen thˆong ma

.nh hay khˆong thˆong qua d¯i

.nh l´y sau:

D

-i

.nh l´y 3.1.3 Cho G= (V, E)l`a d¯ˆo

`thi

.c´o hu

.´o.ng, v`a v∈V. K´y hiˆe

.uG′:= (V, E′)l`a d¯ˆo

`

thi

.c´o hu

.´o.ng nhˆa

.n d¯u

.o.

.c t`u

.Gbˇa

`ng c´ach d¯a

˙’o hu

.´o.ng mˆo

˜i cung trong E. Khi d¯´o Gl`a liˆen

thˆong ma

.nh nˆe

´u v`a chı

˙’ nˆe

´u thuˆa

.t to´an t`ım kiˆe

´m theo chiˆe

`u sˆau trˆen d¯ˆo

`thi

.c´o hu

.´o.ng G,

kho.

˙’ i d¯ˆa

`u t`u

.v, d¯a

.t d¯u

.o.

.c mo

.i d¯ı

˙’nh cu

˙’aGv`a thuˆa

.t to´an t`ım kiˆe

´m theo chiˆe

`u sˆau trˆen d¯ˆo

`thi

.

c´o hu

.´o.ng G′,kho.

˙’ i d¯ˆa

`u t`u

.v, d¯a

.t d¯u

.o.

.c mo

.i d¯ı

˙’nh cu

˙’aG′.

D

-i

.nh ngh˜ıa 3.1.4 D

-ˆo

`thi

.vˆo hu

.´o

.ng Ggo

.i l`a d¯u

.o.

.c d¯i

.nh hu

.´o

.ng ma

.nh nˆe

´u c´o thˆe

˙’ d¯i

.nh hu

.´o

.ng

trˆen c´ac ca

.nh cu

˙’aGsao cho d¯ˆo

`thi

.c´o hu

.´o

.ng tu

.o.ng ´u

.ng nhˆa

.n d¯u

.o.

.c l`a liˆen thˆong ma

.nh.

76

http://www.ebook.edu.vn

D

-i

.nh l´y sau cho ch´ung ta mˆo

.t d¯ˇa

.c tru

.ng cu

˙’a d¯ˆo

`thi

.vˆo hu

.´o

.ng d¯u

.o.

.c d¯i

.nh hu

.´o

.ng ma

.nh.

Ta n´oi cˆa

`utrong d¯ˆo

`thi

.vˆo hu

.´o

.ng liˆen thˆong l`a mˆo

.t ca

.nh m`a bo

˙’ d¯i th`ı d¯ˆo

`thi

.s˜e mˆa

´t t´ınh

liˆen thˆong.

D

-i

.nh l´y 3.1.5 D

-ˆo

`thi

.vˆo hu

.´o.ng Gd¯u

.o.

.c d¯i

.nh hu

.´o.ng ma

.nh nˆe

´u v`a chı

˙’ nˆe

´u n´o liˆen thˆong

v`a khˆong c´o cˆa

`u.

Ch´u

.ng minh. B`ai tˆa

.p. ⊳

Du

.

.a trˆen thuˆa

.t to´an t`ım kiˆe

´m theo chiˆe

`u sˆau, ta c´o thˆe

˙’ d¯i

.nh hu

.´o

.ng c´ac ca

.nh cu

˙’a d¯ˆo

`

thi

.vˆo hu

.´o

.ng d¯u

.o.

.c d¯i

.nh hu

.´o

.ng ma

.nh nhu

.sau. Lˆa

´y mˆo

.t d¯ı

˙’nh bˆa

´t k`y trong d¯ˆo

`thi

.vˆo hu

.´o

.ng

Gl`am d¯ı

˙’nh kho.

˙’ i d¯ˆa

`u v`a thu

.

.c hiˆe

.n thuˆa

.t to´an t`ım kiˆe

´m theo chiˆe

`u sˆau. V`ı d¯ˆo

`thi

.vˆo hu

.´o

.ng

l`a liˆen thˆong, kˆe

´t qua

˙’ cu

˙’a viˆe

.c t`ım kiˆe

´m n`ay cho ta mˆo

.tcˆay bao tr`um1T= (Vn, En),trong

d¯´o Vn={v1, v2, . . . , vn}l`a c´ac d¯ı

˙’nh cu

˙’aG. Nˆe

´ue= (vi, vj) l`a mˆo

.t ca

.nh trong cˆay bao tr`um

T, ta d¯i

.nh hu

.´o

.ng n´o t`u

.d¯ı

˙’nh c´o chı

˙’ sˆo

´nho

˙’ ho.n d¯ˆe

´n d¯ı

˙’nh c´o chı

˙’ sˆo

´l´o

.n ho.n. T´u

.c l`a nˆe

´u

i < j, d¯i

.nh hu

.´o

.ng ca

.nh et`u

.vid¯ˆe

´nvj,v`a nˆe

´uj < i th`ı d¯i

.nh hu

.´o

.ng ca

.nh et`u

.vjd¯ˆe

´nvi.

Nˆe

´u ca

.nh e= (vi, vj) cu

˙’aGkhˆong thuˆo

.c cˆay T, th`ı ta d¯i

.nh hu

.´o

.ng ca

.nh n`ay t`u

.d¯ı

˙’nh c´o chı

˙’

sˆo

´l´o

.n ho.n d¯ˆe

´n d¯ı

˙’nh c´o chı

˙’ sˆo

´nho

˙’ ho.n. T´u

.c l`a nˆe

´ui > j, d¯i

.nh hu

.´o

.ng ca

.nh et`u

.vid¯ˆe

´nvj,

v`a nˆe

´uj > i th`ı d¯i

.nh hu

.´o

.ng ca

.nh et`u

.vjd¯ˆe

´nvi.

H`ınh 3.1 minh ho

.a d¯ˆo

`thi

.vˆo hu

.´o

.ng v`a c´ach d¯i

.nh hu

.´o

.ng n´o.

.......................................................................................................................................................................................................................

.

........................................................................................................................................................................................................................

.

..

.

..

.

..

.

..

.

..

.

.............................................................................................................

.

a

bcd

ef

•

• • •

• •

(a)

.

..

.

..

.

.............................................................................................................

.

..................................................................................................................................................................

.

.......................................................

.

..

.

.............................................................................................................

.

............................................................................................................

.

..

.

..

.

...

.

..

.

...

.

..

.

..

.

..

.

..

.

a

bcd

ef

•

• • •

• •

(b)

H`ınh 3.1: (a) D

-ˆo

`thi

.vˆo hu

.´o

.ng G. (b) D

-ˆo

`thi

.Gd¯u

.o.

.c d¯i

.nh hu

.´o

.ng.

1Kh´ai niˆe

.m n`ay s˜e d¯u

.o

.

.c tr`ınh b`ay trong ??.

77

http://www.ebook.edu.vn

3.2 D

-u

.`o

.ng d¯i ngˇa

´n nhˆa

´t gi˜u

.a hai d¯ı

˙’nh

Cho d¯ˆo

`thi

.c´o hu

.´o

.ng G= (V, E) m`a c´ac cung cu

˙’a n´o d¯u

.o.

.c g´an c´ac tro

.ng lu

.o.

.ng cho bo.

˙’ i ma

trˆa

.n vuˆong cˆa

´pn:W= (wij = (w(vi, vj)).B`ai to´an d¯ˇa

.t ra l`a t`ım d¯u

.`o

.ng d¯i µt`u

.mˆo

.t d¯ı

˙’nh

xuˆa

´t ph´at s∈Vd¯ˆe

´n mˆo

.t d¯ı

˙’nh cuˆo

´i l`a t∈Vsao cho tˆo

˙’ng c´ac tro

.ng lu

.o.

.ng trˆen d¯u

.`o

.ng d¯i µ:

X

ek∈µ

w(ek)

l`a nho

˙’ nhˆa

´t.

C´ac phˆa

`n tu

.

˙’ wij , i, j = 1, ..., n, cu

˙’a ma trˆa

.n tro

.ng lu

.o.

.ng c´o thˆe

˙’ du

.o.ng, ˆam hoˇa

.c bˇa

`ng

khˆong. Mˆo

.t d¯iˆe

`u kiˆe

.n duy nhˆa

´t d¯ˇa

.t ra l`a d¯ˆo

`thi

.c´o hu

.´o

.ng Gkhˆong ch´u

.a c´ac ma

.ch µv´o

.i

tˆo

˙’ng tro

.ng lu

.o.

.ng trˆen ma

.ch µˆam. V`ı rˇa

`ng, nˆe

´u c´o mˆo

.t ma

.ch µnhu

.vˆa

.y v`a vl`a mˆo

.t d¯ı

˙’nh

n`ao d¯´o cu

˙’a n´o, th`ı xuˆa

´t ph´at t`u

.n´ut sta d¯i d¯ˆe

´n d¯ı

˙’nh v, v`a sau d¯´o d¯i v`ong quanh ma

.ch µ

mˆo

.t sˆo

´d¯u

˙’ l´o

.n lˆa

`n rˆo

`i m´o.i d¯ˆe

´ntta s˜e thu d¯u

.o.

.c mˆo

.t d¯u

.`o

.ng d¯i c´o tro

.ng lu

.o.

.ng d¯u

˙’ nho

˙’. V`ı

vˆa

.y, trong tru

.`o

.ng ho.

.p n`ay, d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t l`a khˆong tˆo

`n ta

.i.

Nhˆa

.n x´et rˇa

`ng, nˆe

´u ma trˆa

.n tro

.ng lu

.o.

.ng Wthoa

˙’ m˜an

wij := (1 nˆe

´u (vi, vj)∈E,

0 nˆe

´u ngu

.o

.

.c la

.i,

th`ı d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t t`u

.sd¯ˆe

´ntd¯u

.o

.

.c x´ac d¯i

.nh bˇa

`ng thuˆa

.t to´an t`ım kiˆe

´m theo chiˆe

`u rˆo

.ng

nhu

.d¯˜a tr`ınh b`ay trong phˆa

`n tru

.´o

.c.

Tru

.´o

.c tiˆen ch´ung ta x´et thuˆa

.t to´an Dijkstra, d¯o

.n gia

˙’n v`a rˆa

´t hiˆe

.u qua

˙’, d¯ˆe

˙’ gia

˙’i b`ai to´an

d¯ˇa

.t ra trong tru

.`o

.ng ho.

.p ma trˆa

.n tro

.ng lu

.o.

.ng Wc´o c´ac phˆa

`n tu

.

˙’ khˆong ˆam. Sau d¯´o ph´at

triˆe

˙’n n´o d¯ˆe

˙’ gia

˙’i quyˆe

´t b`ai to´an trong tru

.`o

.ng ho.

.p tˆo

˙’ng qu´at.

3.2.1 Tru

.`o

.ng ho

.

.p ma trˆa

.n tro

.ng lu

.o

.

.ng khˆong ˆam

Thuˆa

.t to´an Dijkstra [20] t`ım d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t t`u

.d¯ı

˙’nh sd¯ˆe

´n d¯ı

˙’nh ttrong d¯ˆo

`thi

.c´o hu

.´o

.ng

c´o tro

.ng lu

.o.

.ng khˆong ˆam. Phu

.o.ng ph´ap n`ay du

.

.a trˆen viˆe

.c g´an c´ac nh˜an ta

.m th`o

.icho c´ac

d¯ı

˙’nh: Nh˜an cu

˙’a d¯ı

˙’nh vi,k´y hiˆe

.uL(vi),l`a mˆo

.t cˆa

.n trˆen cu

˙’a d¯ˆo

.d`ai d¯u

.`o

.ng d¯i t`u

.sd¯ˆe

´nvi.

C´ac nh˜an n`ay sau d¯´o tiˆe

´p tu

.c d¯u

.o.

.c gia

˙’m b´o.t bo.

˙’ i mˆo

.t thu

˙’ tu

.c lˇa

.p v`a ta

.i mˆo

˜i bu

.´o

.c lˇa

.p c´o

d¯´ung mˆo

.t nh˜an ta

.m th`o.i tro.

˙’ th`anh nh˜an cˆo

´d¯i

.nh. Khi d¯ı

˙’nh vid¯u

.o.

.c g´an nh˜an cˆo

´d¯i

.nh th`ı

khˆong thˆe

˙’ gia

˙’mL(vi); sˆo

´n`ay ch´ınh l`a d¯ˆo

.d`ai d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t t`u

.sd¯ˆe

´nvi.

78

http://www.ebook.edu.vn

Thuˆa

.t to´an Dijkstra (wij ≥0)

1. [Kho.

˙’ i ta

.o] D

-ˇa

.t

L(vi) := (0 nˆe

´uvi=s,

+∞nˆe

´u ngu

.o.

.c la

.i.

v´o

.i mo

.ivi∈V. D

-´anh dˆa

´u d¯ı

˙’nh sc´o nh˜an cˆo

´d¯i

.nh, c´ac d¯ı

˙’nh kh´ac c´o nh˜an ta

.m th`o

.i.

D

-ˇa

.tc=s.

2. [Cˆa

.p nhˆa

.t] V´o

.i mo

.ivi∈Γ(c) sao cho vic´o nh˜an ta

.m th`o

.i d¯ˇa

.t

L(vi) := min{L(vi), L(c) + w(c, vi)};

3. T`ım d¯ı

˙’nh vi∗c´o nh˜an ta

.m th`o.i sao cho

L(vi∗) := min{L(vi)<+∞ | vic´o nh˜an ta

.m th`o

.i}.

4. D

-´anh dˆa

´u d¯ı

˙’nh vi∗c´o nh˜an cˆo

´d¯i

.nh v`a d¯ˇa

.tc:= vi∗.

5. (a) (Nˆe

´u t`ım d¯u

.`o

.ng d¯i t`u

.sd¯ˆe

´nt) Nˆe

´uvi=tth`ı thuˆa

.t to´an d`u

.ng, L(t) l`a d¯u

.`o

.ng d¯i

ngˇa

´n nhˆa

´t t`u

.sd¯ˆe

´nt; ngu

.o.

.c la

.i, chuyˆe

˙’n sang Bu

.´o

.c 2.

(b) (Nˆe

´u t`ım tˆa

´t ca

˙’ c´ac d¯u

.`o

.ng d¯i xuˆa

´t ph´at t`u

.s) Nˆe

´u khˆong thˆe

˙’ g´an nh˜an cˆo

´d¯i

.nh

cho d¯ı

˙’nh vi∗trong Bu

.´o

.c 4 th`ı thuˆa

.t to´an d`u

.ng; gi´a tri

.L(vi) cu

˙’a d¯ı

˙’nh vic´o nh˜an cˆo

´

d¯i

.nh cho ta d¯ˆo

.d`ai d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t t`u

.sd¯ˆe

´nvi.Ngu

.o.

.c la

.i chuyˆe

˙’n sang Bu

.´o

.c 2.

D

-i

.nh l´y 3.2.1 Thuˆa

.t to´an Dijkstra cho ta d¯u

.`o.ng d¯i ngˇa

´n nhˆa

´t t`u

.sd¯ˆe

´nt(nˆe

´u c´o).

Ch´u

.ng minh. Tru

.´o

.c hˆe

´t ch´u ´y rˇa

`ng c´ac d¯ı

˙’nh khˆong d¯u

.o.

.c g´an nh˜an cˆo

´d¯i

.nh s˜e khˆong tˆo

`n

ta

.i d¯u

.`o

.ng d¯i t`u

.sd¯ˆe

´n n´o (nh˜u

.ng d¯ı

˙’nh n`ay c´o nh˜an Lbˇa

`ng ∞).

Gia

˙’ su

.

˙’ L(vi) cu

˙’a c´ac d¯ı

˙’nh c´o nh˜an cˆo

´d¯i

.nh o.

˙’ bu

.´o

.c n`ao d¯´o l`a d¯ˆo

.d`ai d¯u

.`o

.ng d¯i ngˇa

´n

nhˆa

´t t`u

.sd¯ˆe

´nvi.K´y hiˆe

.uS1l`a tˆa

.p tˆa

´t ca

˙’ c´ac d¯ı

˙’nh n`ay v`a S2l`a tˆa

.p c´ac d¯ı

˙’nh c´o nh˜an ta

.m

th`o.i. Cuˆo

´i Bu

.´o

.c 2 cu

˙’a mˆo

˜i lˆa

`n lˇa

.p, nh˜an ta

.m th`o

.iL(vi) l`a d¯ˆo

.d`ai d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´tµi

t`u

.sd¯ˆe

´nviqua c´ac d¯ı

˙’nh trong tˆa

.pS1.(V`ı trong mˆo

˜i lˆa

`n lˇa

.p chı

˙’ c´o mˆo

.t d¯ı

˙’nh d¯u

.o.

.c d¯u

.a v`ao

S1nˆen cˆa

.p nhˆa

.t la

.iL(vi) chı

˙’ xa

˙’y ra trong Bu

.´o

.c 2).

X´et d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t t`u

.sd¯ˆe

´nvi∗khˆong ho`an to`an d¯i qua c´ac d¯ı

˙’nh cu

˙’aS1m`a

ch´u

.a ´ıt nhˆa

´t mˆo

.t d¯ı

˙’nh thuˆo

.cS2v`a gia

˙’ su

.

˙’ vj∈S2l`a d¯ı

˙’nh d¯ˆa

`u tiˆen nhu

.vˆa

.y trˆen d¯u

.`o

.ng d¯i

n`ay. Do wij khˆong ˆam, d¯oa

.n d¯u

.`o

.ng d¯i t`u

.vjd¯ˆe

´nvi∗pha

˙’i c´o d¯ˆo

.d`ai ∆ khˆong ˆam sao cho

L(vj)< L(vi∗)−∆< L(vi∗).Tuy nhiˆen d¯iˆe

`u n`ay mˆau thuˆa

˜n v´o

.i khˇa

˙’ng d¯i

.nh rˇa

`ng L(vi∗) c´o

nh˜an ta

.m th`o

.i nho

˙’ nhˆa

´t, v`a do d¯´o c´ac d¯ı

˙’nh trˆen d¯u

.`o

.ng d¯i ngˇa

´n nhˆa

´t d¯ˆe

´nvi∗thuˆo

.cS1v`a

do d¯´o L(vi∗) l`a d¯ˆo

.d`ai cu

˙’a d¯u

.`o

.ng d¯i n`ay.

79

Đồ thị và các thuật toán – Chương 3: Các bài toán về đường đi

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi