Đồ thị và các thuật toán - Chương 3

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

96
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Chương 3 Các bài toán về đường đi

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ thị và các thuật toán - Chương 3

Chu.o.ng 3 C´c b`i to´n vˆ d .`.ng d a ` ¯u o a a e ¯i Trong c´c u.ng dung thu.c tˆ, ta cˆn t` d u.`.ng d i (nˆu c´) gi˜.a hai d ınh cua d` thi. Dˇc ˙ ¯o . - a ´ ` ım ¯ o ´ ¯˙ ’ ’ˆ a´ .e a ¯ eo u . . .`.ng d i ngˇn nhˆ t gi˜.a hai d ınh cua mˆt d` thi c´ y ngh˜ to l´.n. C´ ´ ´u ¯˙ ’ ˙ ’ biˆt, b`i to´n t` d u o e a a ım ¯ ¯ a a o ¯o . o ´ ˆ ıa o o . . ˙ dˆn vˆ b`i to´n nhu. vˆy t`. nhiˆu b`i to´n thu.c tˆ. V´ du, b`i to´n t` h`nh tr` ’a `a ˜e ` ´ thˆe a au e a a .e ı.a a ım a ınh . tiˆt kiˆm nhˆ t (theo tiˆu chuˆ’n khoang c´ch, th`.i gian hoˇc chi ph´ trˆn mˆt ban d` giao ˙ ´e ´ ˙ ’ o ˙ ¯o ’ e a e a a o a ı) e ˆ . . . thˆng; b`i to´n chon phu.o.ng ph´p tiˆt kiˆm nhˆ t dˆ’ d u.a mˆt hˆ d ong lu.c t`. trang th´i ´˙ ´e o a a a e a ¯e ¯ o e ¯ˆ .u. a . . ... ´t nhiˆu phu.o.ng ph´p du.a trˆn l´ thuyˆt d` ` ´ ¯ˆ n`y sang trang th´i kh´c v.v... Hiˆn nay c´ rˆ a a a e oa e a ey eo . . . thi to ra l` c´c phu.o.ng ph´p c´ hiˆu qua nhˆ t. ´ ˙’ ˙ ’a aa aoe . . Chu.o.ng n`y tr` b`y c´c thuˆt to´n t` d u.`.ng d i ngˇn nhˆ t trˆn d` thi c´ trong sˆ. ´ ´ ´ a ınh a a a a ım ¯ o ¯ a a e ¯ˆ . o . o o . Du.`.ng d gi˜.a hai d ˙nh -o ’ 3.1 ¯i u ¯ı Du.`.ng d gi˜.a hai d ˙nh -o ’ 3.1.1 ¯i u ¯ı Trong nhiˆu tru.`.ng ho.p, ch´ng ta cˆn tra l`.i cˆu hoi: Tˆn tai d u.`.ng d i µ t`. d ınh s dˆn ` ` ` . ¯o ´ ˙o a ’ ˙ ’ u ¯˙ ’ e o u a o ¯ ¯e . .´.ng G := (V, E )? Nˆu c´, h˜y chı ra c´ch d i cua d u.`.ng d i µ. d ınh t cua d` thi c´ hu o ´ ¯˙’ ˙ ¯o . o ’ˆ ˙ ’ a ¯ ˙ ¯o ’ eoa ¯ L`.i giai cua b`i to´n n`y kh´ d o.n gian: ch´ng ta chı cˆn ´p dung thuˆt to´n t` kiˆm ˙` a ´ ˙˙aaa ’’ ˙ ’ ’a o a¯ u a a ım e . . theo chiˆu rˆng (hoˇc chiˆu sˆu) trˆn d` thi c´ hu.´.ng G nhu. sau. G´n mˆ i d ınh cua G mˆt ˜’ `o `a o ¯˙ ˙ ’ e. a e e ¯ˆ . o o o a o . . .o.ng ph´p lˇp, dˆn dˆn ta s˜ cho mˆ i d ınh v mˆt chı sˆ n`o d o bˇ ng d o ` ˜’ ˙ o a ¯´ ` ’´ a `` ’´ ˙o o ¯˙ chı sˆ. Bˇ ng phu aa aa e o a ¯ˆ . . . d`i d u.`.ng d i ngˇn nhˆ t (sˆ cung ´ nhˆ t) t`. s t´.i v. D´nh dˆ u d ınh s bˇ ng chı sˆ 0. Nˆu -a ´ ` ´o ´ ´u ´’ ’´ ´ a ¯˙ ˙o a¯o ¯ a a ıt a o a e c´c d ınh d u.o.c d ´nh dˆ u bˇ ng chı sˆ m lˆp th`nh mˆt tˆp ho.p P (m) d a biˆt, th` ta d anh a` ´a ’´ ´ a ¯˙ ’ ¯ . ¯a ˙o a a oa ¯˜ e ı ¯´ . .. . .p: ´ ’´ ˙o . ¯˙’ ˙a ’. dˆ u chı sˆ (m + 1) cho moi d ınh cua tˆp ho a . .a d u.o.c d anh dˆ u | tˆn tai v ∈ P (m) v´.i (v , v ) ∈ E }. ´ `.i P (m + 1) := {vj chu ¯ . ¯´ a o o ij http://www.ebook.edu.vn 75
Thuˆt to´n d`.ng khi khˆng thˆ’ d ´nh dˆ u d u.o.c n˜.a. C´ hai tru.`.ng ho.p xay ra: ˙ ´ ˙ ’ a au o e ¯a a ¯. u o o . . 1. Dınh t d u.o.c d anh dˆ u, chˇng han t ∈ P (m) v´.i m n`o d ´, th` ta x´t c´c d ınh v1 , v2 , ..., -˙ ˙ ’ ´ ’ e a ¯˙ ’ ¯ . ¯´ a a o a ¯o ı . sao cho v1 ∈ P (m − 1), v2 ∈ P (m − 2), . . . , vm ∈ P (0). , ..., v , t} l` d u.`.ng d i phai t` ˙ ım. ’ Khi d o µ := {s = v , v ¯´ a¯ o ¯ m m−1 1 2. Dınh t khˆng d u.o.c d anh dˆ u. Trong tru.`.ng ho.p n`y, ta kˆt luˆn khˆng tˆn tai d u.`.ng -˙ ´ ´a ` .¯o ’ o ¯ . ¯´ a o a e o o . . . s dˆn t. ´ d i t` ¯e ¯u Theo c´ch xˆy du.ng cua thuˆt to´n, dˆ d`ng ch´.ng minh rˇ ng ˜a ` ˙ ’ a a a a e u a . . Mˆnh d` 3.1.1 Nˆu d` thi d u.o.c x´c d. nh bo.i d˜y liˆn tiˆp c´c d ı’nh, th` thuˆt to´n c´ ´o ´ ˙ae ’ e a ¯˙ e ¯ˆ e e ¯ˆ . ¯ . a ¯i ı a ao . . .i gian O(m). th` o -ˆ . e D` thi liˆn thˆng manh 3.1.2 o o . Nhˇc lai l` d` thi c´ hu.´.ng G goi l` liˆn thˆng manh nˆu hai d ınh s v` t t`y y cua G luˆn ´ ´ ¯˙’ a u´˙ ’ a . a ¯o . o o ˆ .ae o e o . .`.ng d i t`. s dˆn t. Hiˆ’n nhiˆn rˇ ng ˙ e` o`. ´ luˆn tˆn tai mˆt d u o o o¯ ¯ u ¯e e a . Dinh l´ 3.1.2 Cho G = (V, E ) l` d` thi c´ hu.´.ng, v` v ∈ V. Khi d ´ G liˆn thˆng manh -. y a ¯ˆ . o o o a ¯o e o . ´u v` chı’ nˆu moi cˇp d ı’nh a, b ∈ V, tˆn tai mˆt d u.`.ng d i t`. a dˆn v v` mˆt d u.`.ng d i t`. ´ `. ´ ˙e ˙ nˆ a e . a¯ o o ¯ o ¯ u ¯e a o¯o ¯ u . . . ´ v dˆn b. ¯e Du.a trˆn thuˆt to´n t` kiˆm theo chiˆu sˆu, ta c´ thˆ’ mˆ ta c´ch x´c d inh mˆt d` ˙ ´ `a o e o˙a ’ e a a ım e e a ¯. o ¯ˆ .o . . .´.ng c´ liˆn thˆng manh hay khˆng thˆng qua d inh l´ sau: thi c´ hu o .o oe o o o ¯. y . Dinh l´ 3.1.3 Cho G = (V, E ) l` d` thi c´ hu.´.ng, v` v ∈ V. K´ hiˆu G := (V, E ) l` d` -. y a ¯ˆ . o o o a ye a ¯ˆ o . thi c´ hu.´.ng nhˆn d u.o.c t`. G bˇ ng c´ch d a o hu.´.ng mˆ i cung trong E. Khi d ´ G l` liˆn ` ˜ a ¯˙ ’ o o a ¯. u a o o ¯o ae . . thˆng manh nˆu v` chı’ nˆu thuˆt to´n t`m kiˆm theo chiˆu sˆu trˆn d` thi c´ hu.´.ng G, ´ ´ ´ `a e a ˙e o a aı e e e ¯ˆ . o o o . . .i d` u t`. v, d at d u.o.c moi d ı’nh cu a G v` thuˆt to´n t`m kiˆm theo chiˆu sˆu trˆn d` thi ´ `a ˙a ’ . ¯˙ ˙ ’ kho ¯ˆ u ¯. ¯ . a aaı e e e ¯ˆ . o . c´ hu.´.ng G , kho.i d` u t`. v, d at d u.o.c moi d ı’nh cu a G . ˙ ¯ˆ u ’a ¯˙ ˙ ’ oo ¯. ¯ . . Dinh ngh˜ 3.1.4 D` thi vˆ hu.´.ng G goi l` d u.o.c d. nh hu.´.ng manh nˆu c´ thˆ’ d .nh hu.´.ng -. -ˆ . o o ˙ ´ ıa o . a ¯ . ¯i o e o e ¯i o . .´.ng tu.o.ng u.ng nhˆn d u.o.c l` liˆn thˆng manh. trˆn c´c canh cua G sao cho d` thi c´ hu o ˙ ’ ea. ¯o . o ˆ ´ a¯. ae o . . http://www.ebook.edu.vn 76
Dinh l´ sau cho ch´ng ta mˆt d ˇc tru.ng cua d` thi vˆ hu.´.ng d u.o.c d inh hu.´.ng manh. -. ˙ ¯ˆ . o o ’o y u o ¯a ¯ . ¯. o .. . Ta n´i cˆu trong d` thi vˆ hu.´.ng liˆn thˆng l` mˆt canh m` bo d i th` d` thi s˜ mˆ t t´ o` ´ a ˙¯ ’ a ¯o . o o ˆ e o ao. ı ¯o . e a ınh ˆ . liˆn thˆng. e o Dinh l´ 3.1.5 D` thi vˆ hu.´.ng G d u.o.c d. nh hu.´.ng manh nˆu v` chı’ nˆu n´ liˆn thˆng -. -ˆ . o ´ ´ e a ˙e oe y o o ¯ . ¯i o o . o` v` khˆng c´ cˆu. ao a Ch´.ng minh. B`i tˆp. u aa . Du.a trˆn thuˆt to´n t` kiˆm theo chiˆu sˆu, ta c´ thˆ’ d .nh hu.´.ng c´c canh cua d` ˙ ´ `a ˙ ¯o ’ˆ e a a ım e e o e ¯i o a. . . .´.ng d u.o.c d inh hu.´.ng manh nhu. sau. Lˆ y mˆt d ınh bˆ t k` trong d` thi vˆ hu.´.ng ´ ´y o ¯˙ .’ thi vˆ hu o .o ¯ . ¯. o a a ¯ˆ . o o o . G l`m d ınh kho.i d` u v` thu.c hiˆn thuˆt to´n t` kiˆm theo chiˆu sˆu. V` d` thi vˆ hu.´.ng ´ `a a ¯˙ ’ ˙ ¯ˆ a . ’a e a a ım e e ı ¯o . o o ˆ . . ´ ´ l` liˆn thˆng, kˆt qua cua viˆc t` kiˆm n`y cho ta mˆt cˆy bao tr`m1 T = (Vn , En ), trong ˙˙ ’’ ae o e e ım e a oa u . . ´ ˙nh cua G. Nˆu e = (vi , vj ) l` mˆt canh trong cˆy bao tr`m ’ ˙ ’ d o Vn = {v1 , v2 , . . . , vn } l` c´c d ı ¯´ aa¯ e ao. a u . T, ta d .nh hu.´.ng n´ t`. d ınh c´ chı sˆ nho ho.n dˆn d ınh c´ chı sˆ l´.n ho.n. T´.c l` nˆu ’´ ´’ ’´ ´ o u ¯˙ ’ o ˙o ˙ ’ ¯e ¯˙ o ˙oo ¯i o uae .´.ng canh e t`. v dˆn v , v` nˆu j < i th` d inh hu.´.ng canh e t`. v dˆn v . ´ ´ ´ i < j, d .nh hu o ¯i u i ¯e j a e ı ¯. o u j ¯e i . . Nˆu canh e = (vi , vj ) cua G khˆng thuˆc cˆy T, th` ta d inh hu.´.ng canh n`y t`. d ınh c´ chı ´ ˙ ’ a u ¯˙ ’ o˙ ’ e. o oa ı ¯. o . . .n ho.n dˆn d ınh c´ chı sˆ nho ho.n. T´.c l` nˆu i > j, d inh hu.´.ng canh e t`. v dˆn v , ´ ´’ ’´ ˙ ´ ´ ¯e ¯˙ o ˙o ’ sˆ l´ oo uae ¯. o u i ¯e j . ´u j > i th` d .nh hu.´.ng canh e t`. vj dˆn vi . ´ v` nˆ ae ı ¯i o u ¯e . H` 3.1 minh hoa d` thi vˆ hu.´.ng v` c´ch d .nh hu.´.ng n´. ınh . ¯ˆ . o o o a a ¯i o o a a • • ...... ...... . . .... .... .... . .... .... . .... .... . ..... .... . ..... . . .... .... .... .... . . . .... . .... .... . ... .... . ... .... .... .... .... . . .... .... ... ... ... ... . . . . . .... . .... .... ... ... .... . . ... ... . . .. ... . . . .... ..... .... ... ... ... ... . . . . .. . . . ...... . .. .... . . ... .... ... ... . .... .... .... . . .... .... .... ... . . ... ... . . ... .. .. . . .... .... . . .... .... ... . . ... ... c c ... . . .. .. . . .... .... . . .... .... ... ... ... . . ... . . .. .. . . ... .... .... . . ... ... .... .... ... . . . . .. .. ... . . ................................................................................ ................................................................................ b• • •d b• • •d ... . . .. ................................................................................. .... .................................................................................. . . ... . .. . . . ..... . ...... .. . .... . . . .. .. .. . .. . .. ..... ........ . ... . . ... . ... . .. ... .. . .. .. .. .. . .. . . .... .. .. ... .... . .... . . . ... ... .... .... ... .... .... . . .... .... . . .. .. . . . ... ... .... . .... .... .... ... ... . . . .... .... .... .... . . . . . . . . .... .... .. . ... . .... . . . ... .. .... .... . . . .... .... ... .... . . . . .... .... . .. .... . . . .... .... .... ....... .... ...... .... ....... ... .... . .... ....... ... . . . . ... . . . . . . . ... .... . ... ..... .. . .. . . . .... ... . . ... ....... . ... .... ....... . . . .. .. .... ....... . .. .... ....... .. . .. . . ... . . . . .... .... ... ... .. .. ... ... ... . . .... .... .... . . .... .... .. .... .... . .... ... .. . . . .... ... .... . .... . . . .... ... ....... ... .... .... . . . . . .... ... . ... .... . . .. ..... . . .. ... . . . .... . ..... .. . .... .... . .... . .... . ....... .... .... . .... . .... . ....... . .... . .... . . ...... . . . . . ..... .. . .. . . ... .......................................................... ... . . • • • • .... ......................................................... .... . . .. .. .. .......................................................... .......................................................... .. .. . . .. .. e e f f (a) (b) H` 3.1: (a) D` thi vˆ hu.´.ng G. (b) D` thi G d u.o.c d .nh hu.´.ng. -ˆ . o o -ˆ . ınh o o ¯ . ¯i o Kh´i niˆm n`y s˜ d u.o.c tr` b`y trong ??. 1 ae a e¯ . ınh a . http://www.ebook.edu.vn 77
Du.`.ng d ngˇn nhˆ t gi˜.a hai d ˙nh -o ´ ´ ’ 3.2 ¯i a a u ¯ı Cho d` thi c´ hu.´.ng G = (V, E ) m` c´c cung cua n´ d u.o.c g´n c´c trong lu.o.ng cho bo.i ma ˙ o¯ . a a ’ ˙ ’ ¯o . o o ˆ aa . . .`.ng d i µ t`. mˆt d ınh ´ u o ¯˙ .’ trˆn vuˆng cˆ p n : W = (wij = (w(vi , vj )). B`i to´n d ˇt ra l` t` d u o a o a a a ¯a a ım ¯ ¯ . . ´t ph´t s ∈ V dˆn mˆt d ınh cuˆi l` t ∈ V sao cho tˆ’ng c´c trong lu.o.ng trˆn d u.`.ng d i µ : ˙ ´ ´a ˙ ’ xuˆa a ¯e o¯ o o a e ¯o ¯ . . . w(ek ) ek ∈µ ´ ˙ ’a l` nho nhˆ t. a C´c phˆn tu. wij , i, j = 1, ..., n, cua ma trˆn trong lu.o.ng c´ thˆ’ du.o.ng, ˆm hoˇc bˇ ng ˙ a` ` a˙ ’ ˙ ’ a a oe a .a . . . .´.ng G khˆng ch´.a c´c mach µ v´.i khˆng. Mˆt d iˆu kiˆn duy nhˆ t d at ra l` d` thi c´ hu o o ¯` ´. o e e a ¯ˇ a ¯ˆ . o o o ua o . . . ˙ng trong lu.o.ng trˆn mach µ ˆm. V` rˇ ng, nˆu c´ mˆt mach µ nhu. vˆy v` v l` mˆt d ınh ’ ` ´oo ˙ ’ tˆ o e a ıa e a a a o¯ . . . . . . . n`o d ´ cua n´, th` xuˆ t ph´t t`. n´t s ta d i dˆn d ınh v, v` sau d o d i v`ng quanh mach µ ´ ´’ a ¯o ˙ o ’ ¯ ¯e ¯˙ ıa auu a ¯´ ¯ o . mˆt sˆ d u l´.n lˆn rˆi m´.i dˆn t ta s˜ thu d u.o.c mˆt d u.`.ng d i c´ trong lu.o.ng d u nho. V` o o ¯˙ o ` ` .´’ ´ ¯˙’ ˙’ a o o ¯e e ¯. o ¯o ¯o. ı . . vˆy, trong tru.`.ng ho.p n`y, d u.`.ng d i ngˇn nhˆ t l` khˆng tˆn tai. ´ ´ `. a o a ¯o ¯ a aa o o . . Nhˆn x´t rˇ ng, nˆu ma trˆn trong lu.o.ng W thoa m˜n ae` ´ ˙a ’ a e a . . . . ´ 1 nˆu (vi , vj ) ∈ E, e wij := nˆu ngu.o.c lai, ´ 0 e .. th` d u.`.ng d i ngˇn nhˆ t t`. s dˆn t d u.o.c x´c d .nh bˇ ng thuˆt to´n t` kiˆm theo chiˆu rˆng ´ ` ´ ´ ¯ . a ¯i ´ `o ı¯ o ¯ a a u ¯e a a a ım e e. . . d ˜ tr` b`y trong phˆn tru.´.c. ` nhu ¯a ınh a a o Tru.´.c tiˆn ch´ng ta x´t thuˆt to´n Dijkstra, d o.n gian v` rˆ t hiˆu qua, dˆ’ giai b`i to´n ’˙’ ´e ˙ aa ’ ˙ ¯e ˙ a a oe u e a a ¯ . . .`.ng ho.p ma trˆn trong lu.o.ng W c´ c´c phˆn tu. khˆng ˆm. Sau d ´ ph´t `a˙ ’ d at ra trong tru o ¯ˇ a oa oa ¯o a . . . . . .`.ng ho.p tˆ’ng qu´t. triˆ’n n´ dˆ’ giai quyˆt b`i to´n trong tru o ˙ ˙’ ˙ ´ e o ¯e ˙ eaa .o a Tru.`.ng ho.p ma trˆn trong lu.o.ng khˆng ˆm 3.2.1 o a o a . . . . Thuˆt to´n Dijkstra [20] t` d u.`.ng d i ngˇn nhˆ t t`. d ınh s dˆn d ınh t trong d` thi c´ hu.´.ng ´ ´ ´’ a u ¯˙ ’ ¯e ¯ ˙ a a ım ¯ o ¯ a ¯o . o o ˆ . .o.ng khˆng ˆm. Phu.o.ng ph´p n`y du.a trˆn viˆc g´n c´c nh˜n tam th`.i cho c´c c´ trong lu . o. oa aa e eaa a. o a . . d ınh: Nh˜n cua d ınh vi , k´ hiˆu L(vi ), l` mˆt cˆn trˆn cua d ˆ d`i d u.`.ng d i t`. s dˆn vi . ´ ¯˙’ ˙ ¯˙ ’ ’ ˙ ¯o a ¯ o ’ a ye aoa e ¯ u ¯e . .. . C´c nh˜n n`y sau d ´ tiˆp tuc d u.o.c giam b´.t bo.i mˆt thu tuc lˇp v` tai mˆ i bu.´.c lˇp c´ ˜ ´ ˙ ’ ˙ ’ ˙. a a. ’ a aa ¯o e . ¯ . o o o oao . . . .i tro. th`nh nh˜n cˆ d inh. Khi d ınh v d u.o.c g´n nh˜n cˆ d inh th` ´ ´ ˙a ’ ¯˙ ’ d ung mˆt nh˜n tam th` ¯´ o a. o a o ¯. ¯. a a o ¯. ı . i ˙ giam L(vi ); sˆ n`y ch´ l` d ˆ d`i d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi . ’˙ ´ ´ ´ ´ khˆng thˆ ’ o e oa ınh a ¯o a ¯ o ¯ a a u ¯e . http://www.ebook.edu.vn 78
Thuˆt to´n Dijkstra (wij ≥ 0) a a . 1. [Kho.i tao] Dˇt ˙ . -a ’ . ´ 0 nˆu vi = s, e L(vi ) := nˆu ngu.o.c lai. ´ +∞ e .. v´.i moi vi ∈ V. D´nh dˆ u d ınh s c´ nh˜n cˆ d .nh, c´c d ınh kh´c c´ nh˜n tam th`.i. -a ´’ ´ a ¯˙ a ¯˙ ’ o o a o ¯i aoa. o . - ˇt c = s. Da. 2. [Cˆp nhˆt] V´.i moi vi ∈ Γ(c) sao cho vi c´ nh˜n tam th`.i d at a a o oa. o ¯ˇ . . . . L(vi ) := min{L(vi ), L(c) + w(c, vi )}; 3. T` d ınh vi∗ c´ nh˜n tam th`.i sao cho ım ¯˙ ’ oa. o L(vi∗ ) := min{L(vi ) < +∞ | vi c´ nh˜n tam th`.i}. oa. o -a ´’ ´ a ¯˙ 4. D´nh dˆ u d ınh vi∗ c´ nh˜n cˆ d .nh v` d ˇt c := vi∗ . o a o ¯i a ¯a. 5. (a) (Nˆu t` d u.`.ng d i t`. s dˆn t) Nˆu vi = t th` thuˆt to´n d`.ng, L(t) l` d u.`.ng d i ´ ´ ´ e ım ¯ o ¯ u ¯e e ı a au a¯ o ¯ . . s dˆn t; ngu.o.c lai, chuyˆ’n sang Bu.´.c 2. ˙ ´ ´ ´ ngˇn nhˆ t t` ¯e a au e o .. (b) (Nˆu t` tˆ t ca c´c d u.`.ng d i xuˆ t ph´t t`. s) Nˆu khˆng thˆ’ g´n nh˜n cˆ d .nh ˙ ´ ´’ ´ ´ ´ e ım a ˙ a ¯ o ¯ a au e o ea a o ¯i .´.c 4 th` thuˆt to´n d`.ng; gi´ tri L(v ) cua d ınh v c´ nh˜n cˆ ´ ˙nh vi∗ trong Bu o ’ ˙ ¯˙ ’ ’ cho d ı ¯ ı a au a. io ao . i .`.ng d i ngˇn nhˆ t t`. s dˆn v . Ngu.o.c lai chuyˆ’n sang Bu.´.c 2. ˙ ´ ´ ´ d .nh cho ta d ˆ d`i d u o ¯i ¯o a ¯ ¯ a a u ¯e i e o . .. Dinh l´ 3.2.1 Thuˆt to´n Dijkstra cho ta d u.`.ng d i ngˇn nhˆ t t`. s dˆn t (nˆu c´). -. ´ ´ ´ ´ y a a ¯o ¯ a a u ¯e eo . Ch´.ng minh. Tru.´.c hˆt ch´ y rˇ ng c´c d ınh khˆng d u.o.c g´n nh˜n cˆ d .nh s˜ khˆng tˆn u´ ` ´ ´ ` a ¯˙’ u oe a o ¯. a a o ¯i eo o .`.ng d i t`. s dˆn n´ (nh˜.ng d ınh n`y c´ nh˜n L bˇ ng ∞). ` ´ ¯˙ ’ tai d u o ¯ ¯ u ¯e o u aoa a . Gia su. L(vi ) cua c´c d ınh c´ nh˜n cˆ d .nh o. bu.´.c n`o d o l` d o d`i d u.`.ng d i ngˇn ´ ´ ˙˙ ’’ ˙ a ¯˙ ’ ’ ˙’ o a o ¯i o a ¯´ a ¯ˆ a ¯ o ¯ a . . s dˆn v . K´ hiˆu S l` tˆp tˆ t ca c´c d ınh n`y v` S l` tˆp c´c d ınh c´ nh˜n tam ´ ´ .´’ nhˆ t t` ¯e i y e 1 a a a ˙ a ¯˙ ’ a a 2 a a a ¯˙ ’ au oa. . . .i. Cuˆi Bu.´.c 2 cua mˆ i lˆn lˇp, nh˜n tam th`.i L(v ) l` d o d`i d u.`.ng d i ngˇn nhˆ t µ ˜a . ´ ´ o` a ´ ˙ ’ th`o o o a. o a ¯ˆ a ¯ o ¯ a ai . i . s dˆn v qua c´c d ınh trong tˆp S . (V` trong mˆ i lˆn lˇp chı c´ mˆt d ınh d u.o.c d u.a v`o ˜` a ´i ˙ ’ ˙ o o ¯˙ ¯ . ¯ ’ ’ t` ¯e u a¯ a1 ı oa . a . . S1 nˆn cˆp nhˆt lai L(vi ) chı xay ra trong Bu.´.c 2). ˙˙ ’’ ea a. o . . X´t d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi∗ khˆng ho`n to`n d i qua c´c d ınh cua S1 m` ´ ´ ´ a ¯˙ ’ ˙ ’ e ¯o ¯ a a u ¯e o a a¯ a .a ´ nhˆ t mˆt d ınh thuˆc S v` gia su. v ∈ S l` d ınh d` u tiˆn nhu. vˆy trˆn d u.`.ng d i ´ o ¯˙ ’ ˙˙j ’’ ˙ ’ ¯a ch´ ıt a u o 2a 2 a¯ ˆ e a e ¯o ¯ . . . n`y. Do wij khˆng ˆm, d oan d u.`.ng d i t`. vj dˆn vi∗ phai c´ d o d`i ∆ khˆng ˆm sao cho ´ ˙ o ¯ˆ a ’ a oa ¯. ¯o ¯u ¯e oa . L(vj ) < L(vi∗ ) − ∆ < L(vi∗ ). Tuy nhiˆn d iˆu n`y mˆu thuˆn v´.i khˇng d .nh rˇ ng L(vi∗ ) c´ ˜ ˙ ’ ` e ¯` ea a ao a ¯i a o .i nho nhˆ t, v` do d o c´c d ınh trˆn d u.`.ng d i ngˇn nhˆ t dˆn v ∗ thuˆc S v` ´ ´a ´´ ˙ ’a ¯´ a ¯˙ ’ nh˜n tam th` a. o e ¯o ¯ a a ¯e i o 1a . do d o L(vi∗ ) l` d ˆ d`i cua d u.`.ng d i n`y. a ¯o a ˙ ¯ o ’ ¯´ ¯a . http://www.ebook.edu.vn 79
V` S1 kho.i tao l` {s} v` trong mˆ i bu.´.c lˇp, d ınh vi∗ d u.o.c thˆm v`o S1 , nˆn bˇ ng ˜ e` ˙.a ’ o a ¯˙ ’ ı a o ¯. e a a . .`.ng d i ngˇn nhˆ t t`. s dˆn v v´.i moi d ınh v ∈ S . Do d o thuˆt ´ ´ ´ ¯˙’ qui nap, L(vi ) l` d ˆ d`i d u o a ¯o a ¯ ¯ a a u ¯e i o ¯´ a . . . . i 1 .i giai tˆi u.u. ’´ ˙o to´n cho l` a o Mˆnh d` 3.2.2 Thuˆt to´n Dijkstra d `i ho i th`.i gian O(n2 ). Nˆu d` thi thu.a v` d u.o.c x´c ´o ¯o ˙ ’o e ¯ˆe aa e ¯ˆ . a¯ . a . . .i d˜y liˆn tiˆp c´c d ı’nh, th` th`.i gian cu.c d ai cu a thuˆt to´n l` O(m log n). ´ ˙ ’ e a ¯˙ ¯. ˙ ’ d. nh bo a e ¯i ıo a aa . . Ch´.ng minh. Trong tru.`.ng ho.p d` thi liˆn thˆng manh d` y d u n d ınh v` cˆn t` d u.`.ng d i a ` ım ¯ o ¯ ¯a ¯ ˙ ¯˙ ’ ’ u o . ¯ˆ . e o o ˆ a . ngˇn nhˆ t t`. s dˆn moi d ınh kh´c, thuˆt to´n cˆn n(n − 1)/2 ph´p cˆng v` so s´nh trong ´ ´ ´ a` ¯˙’ a a u ¯e a a a eo a a . . . .´.c 2 v` n(n − 1)/2 ph´p so s´nh kh´c trong Bu.´.c 3. Ngo`i ra, c´c Bu.´.c 2 v` 3 cˆn x´c a` Bu o a e a a o a a o aa ˙nh d u.o.c g´n nh˜n tam th`.i nˆn cˆn thˆm n(n − 1)/2 ph´p so s´nh. C´c sˆ n`y ` ´ ’ ¯. a d .nh c´c d ı ¯i a¯ a. oea e e a aoa .`.ng d i ngˇn nhˆ t t`. s dˆn t, v` c˜ng l` cˆn trˆn cho sˆ c´c ph´p to´n cˆn thiˆt dˆ’ t` d u o ´˙ ´ ´ a` ´ ´ u aa e oa e a e ¯e ım ¯ ¯ a a u ¯e a . .o.c khi t l` d ınh cuˆi c`ng d u.o.c g´n nh˜n cˆ d inh. ´ ´ a ¯˙ ’ thˆt vˆy, c´c gi´ tri n`y d at d u . aaa a . a ¯. ¯ o u ¯. a a o ¯. .. Khi Thuˆt to´n Dijkstra kˆt th´c, c´c d u.`.ng d i ngˇn nhˆ t d u.o.c x´c d .nh bˇ ng dˆ ´ ` ´ ´ a a e u a ¯o ¯ a a ¯ . a ¯i a ¯e . . .o.ng tr` (3.1) du.´.i d ay. Do d ´ nˆu v l` d ınh tru.´.c d ınh v trong d u.`.ng d i ´ ¯o e i a ¯ ˙ ’ o ¯˙ ’ qui theo Phu ınh o ¯ˆ ¯o ¯ i ngˇn nhˆ t t`. s dˆn vi th` v´.i moi d ınh vi cho tru.´.c, d ınh vi c´ thˆ’ lˆ y l` d ınh m` ˙´ ´ ´ ´ . ¯˙’ o ¯˙ ’ o e a a ¯˙ ’ a a u ¯e ıo a L(vi ) = L(vi ) + w(vi , vi ). (3.1) Nˆu tˆn tai duy nhˆ t d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi th` c´c cung (vi , vi ) trˆn d u.`.ng ´ e`. ´o ´ ´ ´ a ¯o ¯ a a u ¯e ıa e ¯o .´.ng (xem Chu.o.ng 4) v´.i gˆc l` d ınh s. Nˆu c´ nhiˆu ´ ´ ´ eo` ´ o o a ¯˙ ’ d i ngˇn nhˆ t tao th`nh mˆt cˆy c´ hu o ¯ a a. a oao e . .n mˆt d u.`.ng d i ngˇn nhˆ t t`. s dˆn bˆ t k` mˆt d ınh kh´c, th` Phu.o.ng tr` 3.1 s˜ d u.o.c ´ ´ ´´ a u ¯e a y o ¯˙ .’ ho o¯o ¯ a a ı ınh e¯ . . thoa m˜n bo.i ho.n mˆt d ınh kh´c vi v´.i vi n`o d o. ˙a ’ ˙ ’ o ¯˙ ’ a o a ¯´ . Thu tuc sau minh hoa thuˆt to´n Dijkstra. Trong thu tuc n`y, mang M ark [] d u.o.c su. ˙. ’ ˙. a ’ ˙ ’ ¯. ˙ ’ a a . . ˙ d anh dˆ u c´c d ınh c´ nh˜n tam th`.i hay cˆ d .nh: M ark [i] = FALSE nˆu d ınh vi ’ ¯´ ´ a ¯˙ ´ ¯i ´ ¯˙ ’ ’ dung dˆ ¯e a oa. o o e . c´ nh˜n tam th`.i; ngu.o.c lai bˇ ng TRUE. Gi´ tri Label[i] tu.o.ng u.ng nh˜n L( vi ) v` P red[i], ` oa. o a a. ´ a a .. .´.c d ınh v trong d u.`.ng d i ngˇn nhˆ t t`. s dˆn ´ ´ ` ´ ´ sau khi kˆt th´c thuˆt to´n, l` d ınh liˆn tru o ¯˙ a a ¯˙ ’ ’ e u a e ¯o ¯ a a u ¯e . i vi . Nˆu tˆn tai d u.`.ng d i ngˇn nhˆ t t`. s dˆn t, th` thu tuc PathTwoVertex() s˜ in ra thˆng ´ e ` . ¯o ´o ´ ´ ı ˙.’ ¯ a a u ¯e e o tin cua d u.`.ng d i n`y. ˙ ¯o ’ ¯a void Dijkstra(byte Start, byte Terminal) { byte i, Current; AdjPointer Tempt; Path Pred; int Label[MAXVERTICES], NewLabel, Min; Boolean Mark[MAXVERTICES]; http://www.ebook.edu.vn 80
for(i = 1; i Next; while (Tempt != NULL) { if (Mark[Tempt->Vertex] == FALSE) { NewLabel = Label[Current] + Tempt->Length; if (NewLabel < Label[Tempt->Vertex]) { Label[Tempt->Vertex] = NewLabel; Pred[Tempt->Vertex] = Current; } } Tempt = Tempt->Next; } Min = +Infty; for (i = 1; i
return; } Mark[Current] = TRUE; } printf("Ton tai duong di tu %d", Start); printf(" den %d", Terminal); printf("\nDuong di qua cac dinh:"); printf("\n % d " , Start); PathTwoVertex(Pred, Start, Terminal); printf("\nDo dai la: %d ", Label[Terminal]); } Tru.`.ng ho.p ma trˆn trong lu.o.ng tu` y 3.2.2 o a y´ . . . . Thuˆt to´n Dijkstra chı ´p dung trong tru.`.ng ho.p ma trˆn trong lu.o.ng W khˆng ˆm. Tuy ˙a ’ a a o a oa . . . . . . nhiˆn, nhiˆu b`i to´n thu.c tˆ, W l` ma trˆn chi ph´ cho nˆn nh˜.ng cung mang lai lo.i nhuˆn ` ´ e eaa e a a ı, e u a . . .. . .`.ng ho.p n`y, phu.o.ng ph´p cho du.´.i d ay t` d u.`.ng d i ngˇn ´ ˙o ’ phai c´ chi ph´ ˆm. Trong tru o ıa a a o ¯ˆ ım ¯ o ¯ a . nhˆ t t`. s dˆn tˆ t ca c´c d ınh kh´c. Dˆy c˜ng l` phu.o.ng ph´p lˇp v` du.a trˆn c´ch d ´nh a -a u ´ ´´’ a u ¯e a ˙ a ¯ ˙ ’ a aa a. e a ¯a . .´.c lˇp th´. k c´c nh˜n biˆ’u diˆn gi´ tri d o d`i cua c´c d u.`.ng d i ngˇn ˙ ˜ ´ ´ a . ¯ˆ a ˙ a ¯ o ¯ ’ nh˜n, trong d o cuˆi bu o a a ¯´ o u a a e e a . . ´t (t`. s dˆn tˆ t ca c´c d ınh kh´c) c´ sˆ cung khˆng vu.o.t qu´ (k + 1). Thuˆt to´n n`y ´ a ˙ a ¯˙ ´’ ´ ’ nhˆ a u ¯e a oo o a a aa . . d u.a ra lˆn d` u tiˆn bo.i Ford [26] v`o gi˜.a nˇm 1950. Sau d o d u.o.c Moore [45] v` Bellman ` ¯a ˙ ’ ¯ aˆ e a ua ¯´ ¯ . a [3] cai tiˆn nhu. sau. ’´ ˙e Thuˆt to´n Ford, Moore, Bellman a a . K´ hiˆu Lk (vi ) l` nh˜n cua d ınh vi o. cuˆi lˆn lˇp th´. (k + 1). ˙ o` a ´a . a a ˙ ¯˙’ ’ ’ ye u . 1. [Kho.i tao] Dˇt S = Γ(s), k = 1; v` ˙ . -a ’ a .  ´ 0 nˆu vi = s, e  1 ´ w(s, vi ) nˆu vi = s, vi ∈ Γ(s), e L (vi ) :=  nˆu ngu.o.c lai.  ´ +∞ e .. 2. [Cˆp nhˆt nh˜n] V´.i mˆi vi ∈ Γ(S ), vi = s, thay d o’i nh˜n cua n´ theo quy tˇc: ˙ ˜ ´ a˙o ’ a a a oo ¯ˆ a . . Lk+1 (vi ) := min[Lk (vi ), min {Lk (vj ) + w(vj , vi )}], (3.2) vj ∈Ti http://www.ebook.edu.vn 82
trong d o Ti := Γ−1 (vi ) ∩ S. Tˆp S ch´.a tˆ t ca c´c d ınh vi sao cho d u.`.ng d i ngˇn nhˆ t ´ ´’ ´ u a ˙ a ¯˙ ’ ¯´ a ¯o ¯ a a . . s dˆn v c´ sˆ cung l` k. ´ ´ (hiˆn h`nh) t` ¯e i o o ea u a . Tˆp Ti ch´.a tˆ t ca c´c d ınh vj sao cho d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi c´ sˆ cung l` ´ ´’ ´ ´ ´ u a ˙ a ¯˙ ’ a ¯o ¯ a a u ¯e oo a . .c l` v ∈ S ) v` kˆt th´c bˇ ng cung (v , v ). Ch´ y rˇ ng, nˆu v ∈ Γ(S ) th` d u.`.ng ` u´ ` ´ ´ k (t´ a j u ae ua a ei ı¯ o ji ´n nhˆ t t`. s dˆn vi khˆng thˆ’ c´ sˆ cung l` (k + 1) v` ta khˆng thay d ˆ’i nh˜n ˙oo ˙ ´ u ¯e ´ ´ d i ngˇ ¯ a a o e a a o ¯o a ˙ ¯˙ ’’ cua d ınh n`y: a Lk+1 (vi ) := Lk (vi ), v´.i moi vi ∈ Γ(S ). o . 3. [Kiˆ’m tra kˆt th´c] (a) Nˆu k ≤ n − 1 v` Lk+1 (vi ) = Lk (vi ), v´.i moi vi ∈ V, th` thuˆt ˙ ´ ´ e e u e a o ı a . . to´n d`.ng; nh˜n cua d ınh vi cho ta d ˆ d`i d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi . ´ ´ ´ a ˙ ¯˙ ’ ’ au ¯o a ¯ o ¯ a a u ¯e . (b) Nˆu k < n − 1 v` L (v ) = L (v ), v´.i v n`o d o, th` chuyˆ’n sang Bu.´.c 4. ˙ ´ k+1 k e a o a ¯´ ı e o i i i (c) Nˆu k = n − 1 v` L (vi ) = L (vi ), v´.i vi n`o d o, th` d` thi G c´ mach v´.i d o ´ k+1 k e a o a ¯´ ı ¯o . ˆ o. o ¯ˆ . ´ d`i ˆm. Thuˆt to´n kˆt th´c. aa a ae u . -a 4. [Cˆp nhˆt S ] Dˇt a a . . . S := {vi | Lk+1 (vi ) = Lk (vi )}. (Tˆp S bˆy gi`. ch´.a tˆ t ca c´c d ınh m` d u.`.ng d i ngˇn nhˆ t t`. s dˆn n´ c´ sˆ cung ´ ´’ ´ ´ ´ o u a ˙ a ¯˙ ’ a a a¯ o ¯ a a u ¯e o o o . l` (k + 1)). a 5. Thay k bo.i (k + 1) v` lˇp lai Bu.´.c 2. ˙ ’ aa . o . Khi thuˆt to´n kˆt th´c v` d` thi khˆng c´ mach d ˆ d`i ˆm, ch´ng ta c´ thˆ’ t` tˆ t ˙ ´ ´ a ae u a ¯o . o ˆ o . ¯o a a u o e ım a . . .`.ng d i (nˆu tˆn tai) ngˇn nhˆ t t`. s dˆn tˆ t ca c´c d ınh kh´c. Ho.n n˜.a c´c d u.`.ng ´ ca c´c d u o ¯ e ` . ´o ´ ´´’ ˙a¯ ’ a u ¯e a ˙ a ¯˙ ’ a a u a ¯o d i c´ thˆ’ nhˆn d u.o.c tru.c tiˆp nˆu, trong ph´p cˆng v`o c´c nh˜n Lk (vi ) o. Phu.o.ng tr` ˙ ´´ ˙ ’ ¯ o e a ¯. ee eo aa a ınh . . . .u tr˜. thˆng tin mˆ i d ınh trong suˆt qu´ tr` t´ to´n, ˜’ ´ k o ¯˙ 3.2, ta thˆm mˆt nh˜n P (vi ) lu e o a uo o a ınh ınh a . ˙nh kˆ tru.´.c d ınh vi trˆn d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi o. bu.´.c lˇp ´ ` ´ u ¯e ´ k ’ ˙ ’ ˙ ’ trong d ´ P (vi ) l` d ı ¯o a¯ e o¯ e ¯o ¯ a a oa . . k. Ta c´ thˆ’ kho.i tao ˙˙.’ th´ u oe ´ s nˆu vi ∈ Γ(s), e P 1 (vi ) := nˆu ngu.o.c lai. ´ 0 e .. Nh˜n P k (vi ) d u.o.c cˆp nhˆt theo Phu.o.ng tr` 3.2 trong Bu.´.c 2 sao cho P k+1 (vi ) = P k (vi ) a ¯. a a ınh o . . nˆu gi´ tri nho nhˆ t d at d u.o.c o. phˆn tu. d` u tiˆn trong dˆ u ngoˇc cua Phu.o.ng tr` 3.2; ´ ´ ’` ´ ˙ ’ a ¯. ¯ . ˙ a ˙ ¯ˆ ’a a˙ ’ e a. e a ınh . .o.c lai. Nˆu k´ hiˆu P(v ) l` vector d u.o.c xˆy du.ng t`. c´c nh˜n ´ ´ k+1 hoˇc P (vi ) = vj nˆu ngu . . a e eye a ¯. a ua a . . . i P khi kˆt th´c thuˆt to´n, th` d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi nhˆn d u.o.c theo th´. tu. ´ ´ ´ ´ e u a a ı¯o ¯ a a u ¯e a ¯. u. . . ngu.o.c: . s, . . . , P 3 (vi ), P 2 (vi ), P (vi ), vi , trong d o P 2 (vi ) c´ ngh˜ l` P (P (vi )), . . . . ¯´ o ıa a Doan chu.o.ng tr` sau minh hoa thuˆt to´n d ˜ tr` b`y. -. ınh a a ¯a ınh a . . http://www.ebook.edu.vn 83
void Ford_Moore_Bellman(byte Start) { byte i, k, Terminal; AdjPointer Tempt1, Tempt2; Path OldPred, NewPred; int OldLabel[MAXVERTICES], NewLabel[MAXVERTICES], Min; Boolean Done, Mark[MAXVERTICES]; for (i = 1; i Next; while (Tempt1 != NULL) { Mark[Tempt1->Vertex] = TRUE; if (Tempt1->Vertex != Start) { OldPred[Tempt1->Vertex] = Start; OldLabel[Tempt1->Vertex] = Tempt1->Length; } Tempt1 = Tempt1->Next; } for (i = 1; i
while (Tempt1 != NULL) { NewPred[Tempt1->Vertex] = Tempt1->Vertex; Min = OldLabel[Tempt1->Vertex]; Tempt2 = V_in[Tempt1->Vertex]->Next; while (Tempt2 != NULL) { if (Mark[Tempt2->Vertex] == TRUE) { if ((OldLabel[Tempt2->Vertex] + Tempt2->Length) < Min) { NewPred[Tempt1->Vertex] = Tempt2->Vertex; Min = OldLabel[Tempt2->Vertex] + Tempt2->Length; } } Tempt2 = Tempt2->Next; } NewLabel[Tempt1->Vertex] = Min; Tempt1 = Tempt1->Next; } } } Done = TRUE; for (i = 1; i
printf("\n Duong di qua cac dinh:"); printf(" % d " , Start); PathTwoVertex(OldPred, Start, Terminal); i = Terminal; printf(" Do dai la: %d ", OldLabel[Terminal]); printf("\n "); getch(); } else { printf("\n "); printf("Khong ton tai duong di tu %d", Start); printf(" den %d", Terminal); } return; } for (i = 1; i
´ ˙ ’ . ¯˙ ’ Nh˜n cua moi d ınh vi ∈ V l` cˇp (P (vi ), L(vi )). Kˆt th´c thuˆt to´n, L(t) l` d o d`i a aa e u a a a ¯ˆ a . . . .`.ng d i ngˇn nhˆ t t`. s dˆn t v` vector P cho ta thˆng tin cua d u.`.ng d i n`y. ´ ´ ´ ˙¯ ’ ˙ ¯o ’ cua d u o ¯ a a u ¯e a o ¯a 1. [Kho.i tao] Dˇt ˙ . -a ’ . ´ +∞ nˆu vi = s, e L(vi ) := ´ 0 nˆu vi = s, e v` a ´ −1 nˆu vi = s, e P (vi ) := ´ 0 nˆu vi = s, e Kho.i tao Stack chı c´ mˆt phˆn tu. l` s. ` ˙. ’ ˙o o ’ a ˙a ’ . 2. [Bu.´.c lˇp] Trong khi Stack kh´c NULL oa a . { lˆ y ra phˆn tu. vi o. d` u Stack; ´ ` a˙ ’ ˙ ¯ˆ ’a a .i moi d ınh v ∈ V sao cho v ∈ Γ(v ), . ¯˙’ v´o j j i { ´ nˆu [L(vi ) + w(vi , vj ) < L(vj )] th` g´n e ıa { L(vj ) = L(vi ) + w(vi , vj ); P (vj ) = vi ; nˆu d ınh vj chu.a bao gi`. o. trong Stack th` ch`n vj v`o cuˆi Stack; ´’ ´ e ¯˙ o˙ ’ ıe a o ngu.o.c lai, nˆu vj d a t`.ng o. trong Stack, nhu.ng hiˆn tai khˆng c´ trong ´ ˙’ e ¯˜ u e. o o .. . d o th` ch`n vj v`o d` u cua Stack. a ¯a ˙ ’ ¯´ ı e ˆ } } } Du.`.ng d ngˇn nhˆ t gi˜.a tˆ t ca c´c cˇp d ˙nh -o ´ ´ ´’ u a ˙ a a ¯ı ’ 3.3 ¯i a a . Gia su. cˆn phai t` d u.`.ng d i ngˇn nhˆ t gi˜.a hai d ınh t`y y. R˜ r`ng ta c´ thˆ’ giai b`i ˙’ ´ ˙˙` ´u ’’a ˙ ım ¯ o ’ ¯˙ ’ oe˙a ¯ a a u´ oa . dung n lˆn thuˆt to´n mˆ ta o. phˆn tru.´.c, m` trong mˆ i lˆn thu.c ` ˜a ` o ˙˙ ` o` ˙ ’ ’’ to´n n`y bˇ ng c´ch su . aaa a a a a a o a . . ` n lu.o.t l` c´c d ınh cua d` thi. Trong tru.`.ng ho.p d` thi d` y d u c´ ma . a a ¯˙ ’ ˙ ¯o . ’ˆ . ¯ˆ . ¯a ¯ ˙ o ’ hiˆn, ta s˜ chon s lˆ e e. a o o ˆ . trˆn trong lu.o.ng khˆng ˆm, sˆ ph´p t´ cˆn thiˆt tı lˆ v´.i n3 ; tr´i lai v´.i ma trˆn trong o e ınh ` ´ ´ ’. e ˙e o a oa a a.o a . . . . . .o.ng tˆ’ng qu´t, sˆ ph´p t´ tı lˆ v´.i n4 . ˙ ´ a o e ınh ˙ e o ’. lu . o http://www.ebook.edu.vn 87
Trong phˆn n`y ch´ng ta s˜ tr` b`y hai c´ch ho`n to`n kh´c dˆ’ giai b`i to´n t` ˙’ ` a ¯e ˙ a aa u e ınh a a a a a ım .`.ng d i ngˇn nhˆ t gi˜.a tˆ t ca c´c cˇp d ınh. Nh˜.ng phu.o.ng ph´p n`y c´ thˆ’ ´p dung cho ˙ ´ ´ ´’ a u a ˙ a a ¯˙ ’ du o ¯ ¯ a u a a o ea . . c´c ma trˆn trong lu.o.ng tˆ’ng qu´t v` chı d oi hoi sˆ ph´p t´ tı lˆ v´.i n3 . V´.i tru.`.ng ho.p ˙ ’´ a a ˙ ¯` ˙ o e ınh ˙ e o ’ ’. a a o o o . . . . ma trˆn trong lu.o.ng khˆng ˆm, n´i chung, c´c phu.o.ng ph´p n`y s˜ nhanh ho.n 50% c´ch a oa o a aae a . . . ` ´p dung thuˆt to´n Dijkstra n lˆn. a a a a . . Thuˆt to´n Hedetniemi (tru.`.ng ho.p ma trˆn trong lu.o.ng 3.3.1 a a o a . . . . . khˆng ˆm) o a Mˆt trong nh˜.ng muc d´ cua c´c thuˆt to´n t` d u.`.ng d i ngˇn nhˆ t l` x´c d inh tˆ t ca ´ ´ ´’ . ¯ıch ˙ a ’ a˙ o u a a ım ¯ o ¯ a a a a ¯. . . .`.ng d i ngˇn nhˆ t c´ thˆ’ c´ trong mˆt d` thi c´ trong lu.o.ng tai c`ng ˙ ´ ´ a ¯ˆ a ˙ a ¯ ’ c´c d o d`i cua c´c d u o ¯ a a o eo o ¯o . o . .ˆ .u . . .i d iˆ’m. Trong phˆn n`y, ch´ng ta thao luˆn c´ch tiˆp cˆn kh´c giai quyˆt b`i to´n ˙ ` ´. ´ ˙’ ˙ ’ mˆt th` ¯ e o o aa u aa ea a eaa . . n`y (xem [2]). a Thuˆt to´n d u.o.c xˆy du.ng trˆn co. so. mˆt c´ch t´ m´.i l˜y th`.a cua c´c ma trˆn, ˙oa ’. ˙a ’ a a ¯. a e ınh o u u a . . . ˙ng ma trˆn Hedetniemi. Tˆ’ng n`y d u.o.c Hedetniemi tr` b`y v´.i ’ ˙ m` ch´ng ta s˜ goi l` tˆ au e . ao a o a¯. ınh a o . Nystuen tai tru.`.ng d ai hoc Michigan. o ¯. . . X´t d` thi liˆn thˆng c´ trong lu.o.ng G = (V, Γ) v´.i tˆp c´c d ınh V = {v1 , v2 , . . . , vn } o a a ¯˙ ’ e ¯ˆ . e o o o. . . .o.ng khˆng ˆm W := [w ] cˆ p n × n. ´ v` ma trˆn trong lu . a a oa a . . ij Chˇng han, d` thi trong H` 3.2 c´ ma trˆn trong lu.o.ng ˙ ’ a . ¯ˆ . o ınh o a . . .   0 30 ∞ 30 ∞ ∞ ∞ ∞ 40  30 ∞ 0 25 40 ∞ ∞ ∞ ∞     ∞ 25 0 50 ∞ ∞ ∞ ∞ ∞    30 ∞ 40 50 0 30 20 ∞ ∞     W = ∞ ∞ ∞ 30 0 ∞ 25 ∞ ∞.   ∞ 20  ∞ ∞ 20 ∞ 0 20 ∞   ∞ ∞ ∞ ∞ ∞ 25 20 0 25     ∞ ∞ ∞ ∞ ∞ ∞ 25 0 20  40 ∞ ∞ ∞ ∞ 20 ∞ 20 0 Ch´ng ta gi´.i thiˆu mˆt ph´p to´n m´.i trˆn c´c ma trˆn goi l` tˆ’ng ma trˆn Hedet- ˙ u o e o e a oea a . ao a . . . . niemi. Dinh ngh˜ 3.3.1 Gia su. A l` ma trˆn cˆ p m × n v` B l` ma trˆn cˆ p n × p. Tˆ’ng ma -. ˙ ´ ´ ˙˙ ’’ ıa a aa a a aa o . . ´ ˙ ’ trˆn Hedetniemi cua hai ma trˆn A v` B l` ma trˆn C cˆ p m × p, k´ hiˆu A ⊕ B, x´c d .nh a a a a a a ye a ¯i . . . . ˙.i: ’ bo cij := min{ai1 + b1j , ai2 + b2j , . . . , ain + bnj }. http://www.ebook.edu.vn 88
v5 • .. .. .... ....... .... ....... .... .... .... .... .... .... .... .... .... .... .... 25 30 .... ... ... .... .... .... .... .... .... .... .... .... .. .... . .... .... .... .... .. . .... .... .... .... v4 .. .... . .... .... .... 50 .... .... .. . .... .... .... .... .. . .... .... .... v7 • • v3 .... • ......................................................... ......................................................... .... .... . ..... . .. .... .... .... ... . . .. . . .... .... . ..... . .... . ..... . .... . . .... .... . . . .... .... . . . 20 20 . . . ... .... ... .. . .... . . . .... .... . . . .... ... . ... .... . . .. . . . . .... .... .... . . . ... .... . ... . . . .. .... . .... . . . .... .... ... ... . . . .... . . . .... .. . . . . ... .... .... ... .... . . . .... . . . .. . . ... .... ... . . .... .... . .... v6 . . . . . .... . ... .. . ... .... .... . . . .... . . . .... ... . . . .... ... .. . . . . .... .... .... . . . .... ... . ... . . .... ...... .... .... . • . . . ... 25 30 25 . . ... . ... . . . . .. . . . ... ... . . . . . . . . . ... . . 40 . ... . . . . . . . . ... . ... . . . . . . . . . . ... . ... . . . . . . . . . ... . . . ... . . . . . . . . . ... ... . 20 . . . . . . . ... . . . . ... . . . . . . . . ... . ... . . . . . . . . ... . . . . ... . . . ... . . . . ... . . . . . . . . ... . . ... . . . . . . . . . . .... . .... . . • • • • . . . . ................................................................................................................................................................. . . . . ................................................................................................................................................................ . v8 v9 v1 v2 20 40 30 H` 3.2: ınh     012 034 ˙ng ma trˆn A ⊕ B nˆu A =  2 0 3  v` B =  5 0 4  . ’ ´ V´ du 3.3.2 T` tˆ ı. ım o a e a    . 560 310 Ta c´ o       012 034 012      A ⊕ B = 2 0 3 + 5 0 4 = 2 0 3. 560 310 310 Chˇng han, phˆn tu. c23 x´c d .nh bo.i ˙ ’ ` a˙ ’ ˙ ’ a a ¯i . c23 = min{2 + 4, 0 + 4, 3 + 0} = 3.     01∞ 10∞ V´ du 3.3.3 T` tˆ’ng ma trˆn A ⊕ B nˆu A =  1 0 4  v` B =  1 0 4  . ˙ ´ ı. ım o a e a     . ∞40 ∞40 Ta c´ o       01∞ 10∞ 105      A ⊕ B =  1 0 4  +  1 0 4  = 1 0 4. ∞40 ∞40 540 Chˇng han, phˆn tu. c13 x´c d .nh bo.i ˙ ’ ` a˙ ’ ˙ ’ a a ¯i . c23 = min{0 + ∞, 1 + 4, ∞ + 0} = 5. Bˆy gi`. ´p dung tˆ’ng ma trˆn Hedetniemi v`o viˆc t` d u.`.ng d i ngˇn nhˆ t. X´t v´ ˙ ´ ´ a oa o a a e ım ¯ o ¯ a a eı . . . http://www.ebook.edu.vn 89
du trong H` 3.2. K´ hiˆu W 2 := W ⊕ W, W k := W k−1 ⊕ W, k ≥ 2. Khi d o ınh ye ¯´ . .   0 30 55 30 60 50 ∞ 60 40  30 70  0 25 40 70 60 ∞ ∞      55 25 0 50 80 70 ∞ ∞ ∞    30 40  40 50 0 30 20 40 ∞   W =  60 ∞. 2 70 80 30 0 ∞ 25 ∞     ∞ 20  ∞ ∞ 20 ∞ 0 20 ∞   ∞ ∞ ∞ ∞ ∞ 25 20 0 25     ∞ ∞ ∞ ∞ ∞ ∞ 25 0 20  40 ∞ ∞ ∞ ∞ 20 ∞ 20 0 Ch´ng ta h˜y x´t c´ch x´c d inh mˆt phˆn tu. cua ma trˆn W 2 = [aij ] : (2) ` a˙˙ ’’ u aea a ¯. o a . . (2) a13 = min{0 + ∞, 30 + 25, ∞ + 0, 30 + 50, ∞ + ∞, ∞ + ∞, ∞ + ∞, ∞ + ∞, 40 + ∞} = 55. Ch´ y rˇ ng gi´ tri 55 l` tˆ’ng cua 30, d o d`i cua d u.`.ng d i ngˇn nhˆ t v´.i sˆ cung mˆt t`. ˙ u´ ` ´ ´ ´ ˙ ’ ¯ˆ a ˙ ¯ o ’ a a. ao ¯ a aoo ou . . (2) ´’ ´’ ¯˙’ ¯e ¯˙ a˙ ’ ¯ˆ a ˙ ’ o ¯˙ a ¯˙’ d ınh v1 dˆn d ınh v2 , v` cua 25, d o d`i cua cung nˆi d ınh v2 v` d ınh v3 . Do d o a13 l` d o d`i ¯´ a ¯ˆ a . . cua d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v2 v´.i sˆ cung nhiˆu nhˆ t hai. Suy ra W 2 cho ta thˆng ´ ´ ´ ´ ` ´ ˙ ¯o ’ ¯ a au ¯e oo e a o .`.ng d i ngˇn nhˆ t gi˜.a hai d ınh c´ sˆ cung nhiˆu nhˆ t hai. ´ ’´’ ´u ´ ` ´ ˙ a ˙ a ¯ˆ a ¯ ¯˙’ tin cua tˆ t ca c´c d o d`i d u o ¯ a a oo e a . Tu.o.ng tu., W 3 cho ta thˆng tin cua tˆ t ca c´c d o d`i d u.`.ng d i ngˇn nhˆ t gi˜.a hai ´ ’´’ ´u ˙ a ˙ a ¯ˆ a ¯ o o ¯ a a . . d ınh c´ sˆ cung nhiˆu nhˆ t ba, v` vˆn vˆn. Do d` thi c´ n d ınh nˆn c´ nhiˆu nhˆ t (n − 1) ´ ` ´ ` ´ ¯˙’ ¯ˆ . o ¯˙ ’ oo e a aa a o eo e a .`.ng d i ngˇn nhˆ t gi˜.a hai d ınh. Vˆy ´ ´u ¯˙ ’ cung trˆn d u o e¯ ¯ a a a . Dinh l´ 3.3.4 Trong d` thi c´ trong sˆ khˆng ˆm n d ı’nh, phˆn tu. h`ng i cˆt j cu a ma -. ´ ` ¯˙ a ˙a ’ ˙ ’ y ¯ˆ . o . o ooa o . .`.ng d i ngˇn nhˆ t gi˜.a d ı’nh v v` v . ´ ´ n−1 a ¯o a ˙ ¯ ’ a u ¯˙ trˆn Hedetniemi W a l` d ˆ d`i cu a d u o ¯ a iaj . . V´.i d` thi trong H` 3.2 c´ ch´ d ınh, ta c´ o ın ¯˙ ’ o ¯ˆ . o ınh o   0 30 55 30 60 50 70 60 40  30 80 90 70  0 25 40 70 60      55 25 0 50 80 70 90 110 90     30 40 60 40  40 50 0 30 20     8 W =  60 70 80 30 0 45 25 50 65  .    50 20 40 20  60 70 20 45 0    0 25 40   70 80 90 40 25 20     60 90 110 60 50 40 25 0 20  40 70 90 40 65 20 40 20 0 Do d o, d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v7 c´ d o d`i 70. ´ ´ ´ ¯´ ¯ o ¯ a au ¯e o ¯ˆ a . http://www.ebook.edu.vn 90
Diˆu l´ th´ nhˆ t trong v´ du n`y l` W 4 = W 8 . Thˆt vˆy, d ang th´.c suy tru.c tiˆp t`. -` y u a ˙ ’ ´ ´ e ı.aa a a ¯ˇ u eu .. . .`.ng d i ngˇn nhˆ t d i qua nhiˆu nhˆ t bˆn cung. Bo.i vˆy d o d`i ´ d` thi trong H` 3.2: moi d u o ¯ ´ ` ´´ ˙ a ¯ˆ a ’. ¯o . ˆ ınh .¯ a a¯ e ao . .`.ng d i ngˇn nhˆ t d u.o.c x´c d inh bo.i ma trˆn W 4 thay v` phai t´ dˆn W 8 . Tˆ’ng ˙ ´ ´ ´ ˙¯ ’ ˙’ ˙ ınh ¯e ’ cua d u o ¯ a a ¯ . a ¯. a ı o . qu´t ta c´ a o -. Dinh l´ 3.3.5 Trong d` thi c´ trong sˆ khˆng ˆm n d ı’nh, nˆu ma trˆn Hedetniemi W k = ´ ´ ¯˙ y ¯ˆ . o . o ooa e a. ˙u thi tˆp c´c d ˆ d`i cu a c´c d u.`.ng d i ngˇn nhˆ t, v` sˆ ’ ´ ´ ´ k−1 k k+1 k . a a ¯o a ˙ a ¯ o ¯ ’ W , c`n W = W , th` W biˆ o ı e a a ao . . .`.ng d i ngˇn nhˆ t khˆng vu.o.t qu´ k. ˜ ´ ´ cung trˆn mˆ i d u o e o¯ ¯ a a o a . Do d ´, thuˆt to´n n`y c´ thˆ’ d`.ng o. bu.´.c lˇp th´. k < (n − 1). Du.´.i d ay l` d oan ˙ ˙ ’ ¯o a a a o eu oa u o ¯ˆ a ¯ . . . .o.ng tr` minh hoa t´ ma trˆn lu˜ th`.a cua ma trˆn trong lu.o.ng W. yu˙ ’ chu ınh . ınh a a . . . . void Hetdetniemi() { int i, j, k, t; int Old[MAXVERTICES][MAXVERTICES], New[MAXVERTICES][MAXVERTICES]; Boolean Flag; for (i = 1; i
if (Flag == TRUE) break; } } X´c d .nh d .`.ng d ngˇn nhˆ t ´ ´ a ¯i ¯u o ¯i a a Bˆy gi`. ta t` d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v7 (d o d`i 70). Ta c´ ´ ´ ´ a o ım ¯ o ¯ a au ¯e ¯ˆ a o . (4) (3) w14 = w1k ⊕ wk7 v´.i k n`o d o. Nhu.ng c´c phˆn tu. w1k tao th`nh vector h`ng ’ (3) . ` a˙ o a ¯´ a a a (0, 30, 55, 30, 60, 50, 70, 60, 40) v` c´c phˆn tu. wk7 tao th`nh vector cˆt ` a˙ ’ aa a o . . (∞, ∞, ∞, ∞, 25, 20, 0, 25, ∞). V` gi´ tri nho nhˆ t d at d u.o.c tai k = 6 u.ng v´.i 70 = 50 + 20 (v` k = 7) nˆn d u.`.ng d i ngˇn ´ ´ ˙ a ¯. ¯ . . ’ ıa. ´ o a e ¯o ¯ a . v dˆn v s˜ d i qua nhiˆu nhˆ t ba cung t`. v dˆn v v` kˆt th´c v´.i cung d o d`i 20 ´ ´ ` ´ ´ ´ nhˆ t t` 1 ¯e 7 e ¯ au e a u 1 ¯e 6 a e uo ¯ˆ a . . v dˆn v . (Thˆt ra, do gi´ tri nho nhˆ t c˜ng d at d u.o.c tai k = 7 (´.ng v´.i 70 + 0) nˆn ´ ´ ˙ ’ a u ¯. ¯ . . t` 6 ¯e 7 u a a. u o e . ` n tai d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v7 v´.i tˆ’ng sˆ cung d i qua khˆng vu.o.t qu´ ba). ˙ ´ ´u ´ ´ tˆ . ¯ o o ¯ a a ¯e oo o ¯ o a . Tiˆp dˆn ta t` cung tru.´.c khi dˆn d ınh v6 . Ch´ y rˇ ng w16 = 70 − 20 = 50. C´c (4) u´ ` ´´ ´’ ¯e ¯ ˙ e ¯e ım o a a phˆn tu. wk6 tao th`nh vector cˆt ` a˙ ’ a o . . (∞, ∞, ∞, 20, ∞, 0, 20, ∞, 20). Lˆn n`y gi´ tri nho nhˆ t d at tai k = 4 (´.ng v´.i 50 = 30 + 20) nˆn d u.`.ng d i ngˇn nhˆ t d ˆ ´ ` ´ ´. ˙ ’ a ¯. . aa a. u o e ¯o ¯ a a ¯o . v dˆn v kˆt th´c v´.i cung (v , v ) d ˆ d`i 20. Cuˆi c`ng, c´c phˆn tu. w tao ´ ´ ´ ` a ˙ k4 . ’ d`i 50 t` 1 ¯e 6 e a u uo ¯o a ou a . 46 th`nh vector cˆt a o . (30, 40, 50, 0, 30, 20, ∞, ∞, ∞), v` gi´ tri nho nhˆ t d at tai k = 1 hoˇc k = 4 (´.ng v´.i 30 + 0 hoˇc 0 + 30) nˆn tˆn tai cung ´ e`. ˙ ’ a ¯. . aa. a u o a o . . . v dˆn v . Vˆy d u.`.ng d i ngˇn nhˆ t t`. v dˆn v l` v , v , v , v (c´c cung c´ ´ ´ ´ ´ d o d`i 30 t` 1 ¯e 4 a ¯ o ¯ˆ a u ¯ a a u 1 ¯e 7 a 1 4 6 7 a o . . d o d`i 30, 20, 20). ¯ˆ a . Do d ´ thuˆt to´n Hedetniemi cho mˆt minh hoa h` hoc trong mˆ i bu.´.c lˇp, v` su. ˜ a˙ ’ ¯o a a o . ınh . o oa . . . ˙ phuc hˆi d u.o.c d u.`.ng d i ngˇn nhˆ t. Nhu. vˆy, ch´ng ta cˆn thˆm ’ . `¯. ¯o ´ ´ ` dung c´c ma trˆn c´ thˆ a aoe o ¯ a a a u a e . . . mˆt ma trˆn P lu.u tr˜. thˆng tin cua c´c d u.`.ng d i ngˇn nhˆ t. Ma trˆn n`y s˜ d u.o.c cˆp ´ ´ ˙ a ¯o ’ o a uo ¯ a a a a e¯ . a . . . . nhˆt trong mˆ i bu.´.c lˇp khi t´ W k t`. W k−1 . ˜ a o oa ınh u . . http://www.ebook.edu.vn 92
Thuˆt to´n Floyd (tru.`.ng ho.p ma trˆn trong lu.o.ng tu` y) 3.3.2 a a o a y´ . . . . . Thuˆt to´n du.´.i d ay d u.o.c d u.a ra lˆn d` u tiˆn bo.i Floyd [25] v` d u.o.c l`m min ho.n bo.i ` ¯ˆ ˙ ’ ˙ ’ a a o ¯ˆ ¯ . ¯ a a e a¯ . a . . Murchland [46]. Thuˆt to´n Floyd a a . 1. [Kho.i tao] Dˇt k := 0. ˙ . -a ’ . 2. k := k + 1. 3. [Bu.´.c lˇp] V´.i moi i = k sao cho wik = ∞ v` v´.i moi j = k sao cho wkj = ∞, thu.c oa o ao . . . . hiˆn ph´p g´n e ea . wij := min{wij , (wik + wkj )}. (3.3) 4. [Diˆu kiˆn kˆt th´c] (a) Nˆu tˆn tai chı sˆ i sao cho wii < 0 th` tˆn tai mach v´.i d ˆ -` ´ e`. ´o ’´ ı` . ˙o e ee u o o ¯o . . . .a d ınh v . B`i to´n vˆ nghiˆm; thuˆt to´n d`.ng. d`i ˆm ch´ ¯˙ ’ aa u aao e a au . . i (b) Nˆu wii ≥ 0 v´.i moi i = 1, 2, . . . , n, v` k = n, b`i to´n c´ l`.i giai: ma trˆn wij cho ´ ˙ ’ e o a a a oo a . . .`.ng d i ngˇn nhˆ t t`. v dˆn v . Thuˆt to´n d`.ng. ´ ´ ´ d ˆ d`i d u o ¯o a ¯ ¯ a a u i ¯e j a au . . ´u wii ≥ 0 v´.i moi i = 1, 2, . . . , n, nhu.ng k < n, chuyˆ’n sang Bu.´.c 2. ˙ (c) Nˆe o e o . Ch´.ng minh t´ d ung d ˇn cua thuˆt to´n Floyd l` ho`n to`n d o.n gian [35], [25] v` ´ ˙ ’ ˙ ’ u ınh ¯´ ¯a a a aa a¯ a . .`.i d oc. Ph´p to´n co. ban cua Phu.o.ng tr` 3.3 trong thuˆt to´n n`y goi l` ˙ ’ ˙ ’ d`nh cho ngu o ¯ . a e a ınh a a a .a . ph´p to´n bˆ ba v` c´ nhiˆu u.ng dung trong nh˜.ng b`i to´n tu.o.ng tu. b`i to´n t` d u.`.ng `´ e ao ao e u aa a a ım ¯ o . . . ´ ´ d i ngˇn nhˆ t (xem [14], [30]). ¯ a a C´c d u.`.ng d i ngˇn nhˆ t c´ thˆ’ nhˆn d u.o.c d` ng th`.i c`ng v´.i c´c d o d`i d u.`.ng d i ˙ ´ ´ a ¯o ¯ a a o e a ¯ . ¯ˆ o ou o a ¯ˆ a ¯ o ¯ . . . dung quan hˆ dˆ qui tu.o.ng tu. Phu.o.ng tr` 3.2. Bˇ ng c´ch ´p ´ a` ` ´a ˙ ’ ngˇn nhˆ t bˇ ng c´ch su . a a e ¯e ınh a aa .. . . chˆ cua Hu [35] dˆ’ lu.u gi˜. thˆng tin c´c d u.`.ng d i ngˇn nhˆ t c`ng v´.i d o d`i cua ˙ ´ ´˙ ´u ’ o ¯ˆ a ˙ ’ dung co e ¯e uo a ¯o ¯ a a . . .a v`o ma trˆn vuˆng cˆ p n : P := [θ ]; v` biˆn d ˆ’i n´ d` ng th`.i v´.i viˆc n´. Cu thˆ’ l` d u a ˙ ˙ ´ ´ o . e a¯ a o a a e ¯o o ¯o ˆ ooe . . ij ˙i ma trˆn W. Phˆn tu. θij cua ma trˆn P s˜ chı ra d ınh d i tru.´.c vj trong d u.`.ng d i ’ ´ ` a˙ ’ ˙’ e˙ ’ ¯˙ ’¯ biˆn d ˆ e ¯o a a o ¯o ¯ . . ngˇn nhˆ t t`. vi dˆn vj ; o. bu.´.c d` u tiˆn ta g´n cho ma trˆn P c´c gi´ tri d` u l` θij := vi ´ ´ ´ ˙ ’ a au ¯e o ¯ˆ a e a a a a . ¯a a ˆ . v´.i moi d ınh vi v` vj . ¯˙ ’ o a . C`ng v´.i viˆc biˆn d o’i ma trˆn W theo Phu.o.ng tr` 3.3 trong Bu.´.c 3, ta biˆn d o’i ˙ ˙ ´ ´ u oe e ¯ˆ a ınh o e ¯ˆ . . ´ P theo quy tˇc a ´ θkj nˆu (wik + wkj ) < wij , e θij := nˆu ngu.o.c lai. ´ θij e .. .o.c s˜ gi´p cho ta viˆc t` c´c d u.`.ng d i ngˇn nhˆ t. ´ ´ ´ Kˆt th´c thuˆt to´n, ma trˆn P thu d u . e u e u a a a ¯ e ım a ¯ o ¯ a a . . . ˙ ng han d u.`.ng d i ngˇn nhˆ t gi˜.a hai d ınh vi v` vj l` ’ ´ ´u ¯˙ ’ Chˇa . ¯o ¯ a a a a vi , v ν , . . . , v γ , v β , v α , v j http://www.ebook.edu.vn 93
´ trong d o vα = θij , vβ = θiα , vγ = θiβ , ..., cho dˆn khi vi = θiν . ¯´ ¯e Cˆn ch´ y o. d ˆy l` nˆu tˆ t ca c´c gi´ tri wii d u.o.c kho.i tao bˇ ng ∞ (thay cho bˇ ng ˙.` ` ` ´´’ u ´ ˙ ¯a a e a ˙ a ’ ’ a a. ¯. a a ´ ´ ´ ´ ˙ ’ a ¯o a ˙ ’ 0) l´c xuˆ t ph´t thuˆt to´n, th` c´c gi´ tri cuˆi c`ng cua wii l` d ˆ d`i cua mach ngˇn nhˆ t u a a a a ıa a.ou a a . . . ´t ph´t t`. d ınh vi . Ngo`i ra c˜ng c´ thˆ’ dˆ d`ng x´c d inh mach c´ d o d`i ˆm khi wii < 0 ˙˜a ˙ ’ xuˆ a a u¯ a u o ee a ¯. o ¯ˆ a a . . du.a v`o ma trˆn d u.`.ng d i P. a a ¯o ¯ . . ˙. ’ Thu tuc Floyd() sau minh hoa thuˆt to´n d a tr` b`y. a a ¯˜ ınh a . . void Floyd() { byte i, j, k; AdjPointer Tempt; byte Pred[MAXVERTICES][MAXVERTICES]; int Weight[MAXVERTICES][MAXVERTICES], NewLabel; byte Start, Terminal; for (i = 1; i Length; Tempt = Tempt->Next; } } for (k = 1; k