Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
L I NÓI Đ U
Ờ
Ầ
ừ Lý thuy t đ th là m t lĩnh v c nghiên c u đã có t ụ ự ơ ả ủ ườ ệ ạ ầ ủ lâu đ ivà có nhi u ề ờ ứ ng c b n c a lý thuy t đ th đ ế ồ ị ươ ề ấ ừ c đ xu t t i Th y Sĩ Leonhard i l c ng ụ ọ ỗ ạ i bài toán n i ti ng v các cái ổ ế ộ t ư ưở ở ử ụ ồ ị ể ả ề ố ế ồ ị ng d ng hi n đ i.Nh ng t ứ ữ nh ng năm đ u c a th k 18 b i nhà toán h c l ế ỷ ữ i đã s d ng đ th đ gi Euler.Chính ông là ng ườ c u ầ ở c s d ng đ gi i quy t các bài toán trong nhi u lĩnh v c khác ự ế ề ể ạ thàng ph Konigsberg. Đ th đ ồ ị ượ ử ụ ồ ị ạ ẳ ệ ạ ệ ớ i tích m ch đi n.Chúng ta có th phân bi ứ ị ể ể ấ ề ấ ạ ồ ị ủ ạ ư ạ i các bài toán nh : tìm đ ể ả ạ ộ ố ố ầ ố ề ậ ị ể ờ ể ả ấ nhau .Ch ng h n , đ th có th s d ng đ xác đ nh các m ch vòng trong v n ị ể ử ụ ọ ữ ơ t các h p ch t hoá h c h u c đ gi ể ợ ề ả ử ờ khác nhau v i cùng công th c phân t nh nh ng khác nhau v c u trúc phân t ử ư ổ đ th .Chúng ta có th xác đ nh xem hai máy tính trong m ng có th trao đ i ồ ị Đ thồ ị c v i nhau hay không nh mô hình đ th c a m ng máy tính. thông tin đ ờ ượ ớ ng đi có tr ng s trên các c nh có th s d ng đ gi ườ ể ử ụ ố ọ ng n nh t gi a hai thành ph trong cùng m t m ng giao thông . Chúng ta còn s ử ấ ữ ắ i các bài toán v l p l ch,th i khoá bi u,và phân b t n s cho d ng đ th đ gi ồ ị ể ả ụ các tr m phát thanh và truy n hình.... ề ạ ể ụ ơ ả ệ M c đích ta tìm hi u là nh m gi ủ ụ ấ ọ ỏ ng đi ng n nh t... và nh ng thu t toán đ gi ằ ớ ế ồ ị ữ ắ ấ ườ i thi u các khái ni m c b n,các bài toán ng d ng quan tr ng c a lý thuy t đ th nh bài toán cây khung nh nh t , bài c ượ ng trình trên ệ ư ậ t cùng v i vi c phân tích và h ướ i quy t chúng đã đ ươ ể ả ế ng d n cài đ t ch ẫ ế ệ ặ ớ
C ng c và rèn luy n k năng l p trình, nh l ệ ỹ ớ ạ ậ ặ i các thu t toán mà đ c ậ ứ toán tìm đ trình bày chi ti máy tính. ủ ố t là thu t toán Dijkstra. bi ệ ế ề ậ ườ ng đi ng n nh t. ắ ấ ậ Ch Ch Ch ng 1 : Lý thuy t v thu t toán tìm đ ng 2 : Xây d ng thu t toán. ự ng 3 : Cài đ t thu t toán. ặ ậ ậ ươ ươ ươ
http://vuson.tk - Trang 1 -
Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
Ch ng I : ươ LÝ THUY T V THU T TOÁN TÌM Đ
Ế
Ề
ƯỜ
Ắ NG ĐI NG N
Ậ NH TẤ
ệ I.1 Các khái ni m c b n c a lý thuy t đ th ế ồ ị ơ ả ủ I.1.1 Đ nh nghĩa đ th ồ ị Đ th là m t c u trúc r i r c bao g m các đ nh và các c nh n i các ị ồ ị ộ ấ ờ ạ ạ ồ ố ỉ ở ệ ể ỉ ạ ồ ị ủ ồ ị ố ượ ạ i c t ể
ả ể ả ử ạ ố ể ể ở ạ ố ạ ở ộ ệ ễ t các lo i đ th khác nhau b i ki u và s đ nh này.Chúng ta phân bi ỉ ng c nh n i hai đ nh nào đó c a đ th . Đ có th hình dung đ l ố ể ạ ượ i c n đ n sao l ế ạ ầ các lo i đ th khác nhau ,chúng ta s nêu ví d s d ng chúng đ mô t ụ ử ụ ạ ồ ị ẽ s ta có m t m ng g m các máy tính và các kênh m t m ng máy tính .Gi ồ ộ ạ đi n tho i(g i t t là tên tho i) n i các máy tính này.Chúng ta có th bi u ạ ọ ắ di n các v trí đ t máy tính b i các đi m và các kênh tho i n i chúng b i ể ặ ị các đo n n i,xem hình 1 ố ạ Hà Tây Đ ng Nai ồ An Giang Huế
Hà N i TPHCM Bình Đ nh ộ ị
Quãng Ngãi Phú Yên Khánh Hòa
Hình 1.S đ m ng máy tính ơ ồ ạ
ấ ậ ấ ấ ằ ộ ỉ ạ ả ạ ạ ố ạ
ạ ượ ố ớ ng c g i là ề Nh n th y r ng trong m ng hình 1, gi a hai máy tính b t kỳ ch cho phép nhi u ữ nh t là m t kênh tho i n i chúng,kênh tho i này cho phép liên l c c hai chi u và ề không có máy tính nào l hình 1 đ ượ ọ c n i v i chính nó.S đ m ng máy tính cho tronh ơ ồ ạ ướ => ta đi đ n đ nh nghĩa sau: ị ế i đ đ n đ th vô h ồ ị ơ
. Đ n đ th vô h ị ơ ậ ng G=(V,E) bao g m V là t p đ nh,và E là t p ồ ỉ ướ g m hai ph n t khác nhau c a V g i là các c nh. Đ nh nghĩa 1 các c p không có th t ặ ồ ị ứ ự ồ ầ ử ủ ạ ậ ọ
ả ề i nhi u ườ ợ i ta ph i n i hai máy này b i nhi u kênh tho i . M ng v i đa kênh ề ng xuyên ph i truy n t ề ả ớ ạ ạ ở ng h p gi a hai máy tính nào đó th Trong tr ữ ườ thông tin ng ả ố ườ tho i gi a các máy tính đ c cho trong hình 2. ượ ữ ạ
http://vuson.tk - Trang 2 -
Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
Hà Tây Đ ng Nai Hu An Giang ồ ế
Hà N i HCM ộ Bình Đ nhị
Quãng Ngãi Phú Yên
Hình 2. S đ m ng máy tính v i đa kênh tho i ạ ơ ồ ạ Khánh Hòa ớ
1 va e2 đ
. Đa đ th vô h ồ ị ướ ậ ồ ỉ ặ ầ ử g m hai ph n t ứ ự ồ c g i là c nh l pn u chúng cùng t ặ ế ng G=(V,E) bao g m V là t p các đ nh , và E là khác nhau c a V g i là các c nh ạ ọ ủ ớ ộ ặ ng ng v i m t c p ươ ứ ạ Đ nh nghĩa 2 ị h các c p không có th t ọ .Hai c nh eạ ượ ọ đ nh. ỉ
Hà Tây Đ ng Nai Hu An Giang ồ ế
Hà N i TPHCM Bình Đ nh ộ ị
Quãng Ngãi Phú Yên Khánh Hòa
Hình 3. S đ m ng máy tính v i kênh thông báo. ơ ồ ạ ớ
ồ ị ỗ ơ ồ ị ề ư ề ồ ị ồ ị ồ ị ộ ặ ơ ạ ả ố ỉ
ữ ạ ộ ạ ố ạ ể ụ ẳ ớ c cho trong hình ư ậ ượ ữ c m ng nh v y, b i vì có nh ng đ ả ượ ư ậ ạ ầ ử ộ ỉ ườ ư ậ ng h p này chúng ta c n s ợ c đ nh nghĩa nh sau: đ th vô h ng, đ Rõ ràng m i đ n đ th đ u là đa đ th , nh ng không ph i đa đ th nào cũng là đ n đ th , vì trong đa đ th có hai hay nhi u h n c nh n i m t c p đ nh nào ơ đó. Trong m ng máy tính có th có nh ng kênh tho i n i m t máy tính nào đó v i ớ chính nó(ch ng h n v i m c đích thông báo).M ng nh v y đ ạ 3.Nh v y đa đ th không th mô t ồ ị ở ể khuyên (c nh n i m t đ nh vói chính nó).Trong tr ố ạ d ng đ n khái ni m gi ượ ị ụ ả ồ ị ướ ư ệ ế
http://vuson.tk - Trang 3 -
Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
. Gi ướ ỉ ng G=(V,E) bao g m V là t p các đ nh, và E là t ph i khác nhau) ấ ầ ử ả đ th vô h Đ nh nghĩa 3 ả ồ ị ị h các c p không có th t ứ ự ồ ọ c a V g i là các c nh.C nh e đ ạ ủ ậ ồ (không nh t thi ế c g i là khuy n n u có d ng e=(u,u). ạ g m hai ph n t ượ ọ ế ế ặ ọ ạ
ạ ạ ạ ề ể ậ ừ ộ ỉ ẳ ươ ủ ở ể ử ộ ố ể ỉ Hà N i ch có th nh n tin t ạ ng ng ỉ c thay th b i hai c nh có h ề ượ ế ở ướ ượ ạ ả ộ Các kênh tho i trong m ng máy tính có th ch cho phép truy n tin theo m t các máy chi u.Ch ng h n trong hình 4 máy ch ề ng, có m t s máy ch có th g i tin đi ,còn các kênh tho i cho phép đ a ph ở ị ề c chi u truy n tin theo c hai chi u đ ề nhau.
Hà Tây Đ ng Nai Hu An Giang ồ ế
Hà N i TPHCM Bình Đ nh ộ ị
Phú Yên Khánh Hòa
Hình 4. M ng máy tính v i các kênh tho i m t chi u ề ớ ạ ộ ạ Ta đi đ n đ nh nghĩa sau: ị ế
ướ ậ ỉ Đ nh nghĩa 4 ị t p các c p có th t ặ ậ . Đ n đ th có h ồ ị ơ g m hai ph n t ứ ự ồ ng G=(V,E)bao g m V là t p các đ nh, và E là khác nhau c a V g i là các cung. ầ ử ồ ủ ọ
ế ẽ ả ử ụ ề ế ộ N u trong m ng có th có đa kênh tho i m t chi u,ta s ph i s d ng đ n khái ạ ni m ệ đa đ th có h ể ng: ướ ạ ồ ị
1
ị ậ ồ ỉ ọ Đa đ th có h ồ ị ứ ự ồ ướ ầ ử c g i là cung l p. Đ nh nghĩa 5. các c p có th t ặ va e2 t ươ ứ g m hai ph n t ng ng v i cùng m t c p đ nh đ ộ ặ ớ ngG=(V,E) bao g m V là t p các đ nh,và E là h khác nhau c a V g i là các cung.Hai cung e ọ ỉ ủ ượ ọ ặ
ơ ẽ ồ ị ng.Vì v y, đ cho ng n g n , ta s b qua tính t ắ ọ ệ ớ ơ ẽ ỏ ủ ế ậ ể ướ ng ỗ đ n m i
Trong các ph n ti p theo ch y u chúng ta s làm vi c v i đ n đ th vô h ế ầ và đ n đ th có h ừ ơ ướ ồ ị khi nh c đ n chúng. ắ ế I.1.2. Các thu t ng c b n ậ ữ ơ ả
http://vuson.tk - Trang 4 -
Đ án c s GVHD: Đoàn Văn Th ng ắ ơ ở ồ
Trong m c này chúng ta s trình bày m t s thu t ng c b n c a lý ẽ ậ ộ ố c tiên ,ta xét các thu t ng mô t ả ữ ậ ữ ơ ả ủ các đ nh và c nh c a đ th ạ ủ ồ ị ỉ ụ thuy t đ th .Tr ng. vô h ế ồ ị ướ ướ
ỉ ị ủ ồ ị ượ ọ ướ Hai đ nh u va v c a đ th có h ạ ế ủ ồ ị ng G đ ủ ồ ị ạ ố ỉ ạ ỉ ỉ c g i là các đ nh đ u c a c nh (u,v). ế c g i là k nhau n u Đ nh nghĩa 1. ề (u,v) là c nh c a đ th G.N u e=(u,v) là c nh c a đ th thì ta nói c nh này là ạ c nh liên thu c v i hai đ nh u và v, ho c cũng nói là c nh e n i đ nh u và đ nh v, ộ ớ ặ ạ đ ng th i các đ nh u và v s đ ỉ ồ ẽ ượ ọ ầ ủ ạ ờ ỉ
t có bao nhiêu c nh liên thu c v i m t đ nh , ta đ a vào đ nh nghĩa ộ ớ ộ ỉ ư ạ ị ể ế Đ có th bi ể sau :
. Ta g i b c c a đ nh v trong đ th vô h ọ ậ ủ ỉ ồ ị ướ ộ nglà s c nh liên thu c ố ạ ẽ ệ Đ nh nghĩa 2 ị v i nó ta s kí hi u là deg(v). ớ b c d
a f e g
Hình 1. Đ th vô h ng ồ ị ướ
Thí d . Xét đ th cho trong hình 1, ta có ụ
.Trong ví d trên ồ ị deg(a)=1, deg(b)=4 , deg(c)=4 , deg(f)=3, deg(d)=1 , deg(e)=3 , deg(g)=0. cô l pậ , đ nh b c 1 đ ỉ ọ đ nh treo ỉ ượ ọ ỉ ậ ụ Đ nh b c 0 g i là đ nh ậ ỉ đ nh g là đ nh cô l p, a và d là các đ nh treo. B c c a đ nh có tính ch t sau : ỉ ỉ c g i là ậ ủ ỉ ấ ậ ỉ
Đ nh lý 1 . Gi ị ả ử ướ ng v i m c nh . Khi đó ạ ớ ồ ị
s G=(V,E) là đ th vô h 2m=∑ deg(v) v ˛ V
Rõ ràng trong m i c nh e=(u,v) đ ỗ ạ ượ ấ ả ừ ổ c tính m t l n trong deg(u) và ộ ầ ầ t c các b c c a các đ nh b ng hai l n ỉ ậ ủ ằ Ch ng minh. ứ m t l n trong deg(v). T đó suy ra t ng t ộ ầ s c nh ố ạ
ạ ậ ỉ Thí d 2. ụ Đ th v i n đ nh và m i đ nh có b c là 6 có bao nhiêu c nh ? ỗ ỉ i: Theo đ nh lý 1,ta có 2m=6n.T đó suy ra s c nh c a đ th là 3n. Gi ừ ồ ị ớ ị ủ ồ ị ố ạ ả
http://vuson.tk - Trang 5 -
Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
ướ ộ ng,s đ nh b c l (nghĩa là có b c là s l ) là m t ậ ẻ ố ẻ ố ỉ ậ ồ ị H quệ ả. Trong đ th vô h s ch n. ố ẵ
U
. Th c v y, g i O và U t ứ ự ậ ọ ươ ứ ng ng là t p đ nh b c l ậ ậ ẻ ỉ và t p đ nh ậ ỉ Ch ng minh b c ch n c a đ th ,ta có ẵ ậ ủ ồ ị
v ˛ ỉ
trên là s ổ ố ứ ấ ừ ổ ả ồ , nên t ng này ph i g m ủ ẵ ả ộ ố ẵ ỉ ổ ố ẵ Ta xét các thu t ng t ng t 2m=∑deg(v)= ∑deg(v)+ ∑deg(v) v ˛ O v ˛ V Do deg(v) là ch nv i v là đ nh trong U nên t ng th hai trong v ph i ứ ẵ ớ ế ả ở ch n.T đó suy ra t ng th nh t(chính là t ng b c c a các đ nh b c l ) cũng ậ ủ ổ ậ ẻ t c các s h ng c a nó là s l ph i là s ch n, do t ố ẻ ấ ả ố ẵ ph i là s ch n. m t s ch n các s h ng.Vì v y , s đ nh b cl ậ ẻ ả ố ỉ cho đ th có h ng. ồ ị ự ố ạ ậ ữ ươ ố ạ ậ ướ
ị ế ỉ
Đinh u (v) s đ
N u e=(u,v) là cung c a đ th có h ố ỉ ề ỏ ỉ ủ ầ ố ỉ ỉ
ng t ậ ng ta có khái ni m bán b c ố ớ ồ ị ướ ệ ệ ậ ng G thì ta nói hai đ nh u và Đ nh nghĩa 3. ướ ủ ồ ị vlà k nhau,và nói cung(u,v) n i đ nh u v i đ nh v ho c cũng nói cung này là đi ra ớ ỉ ặ kh i đ nh u và đi vào đ nh v. c g i là đ nh đ u (cu i) c a cung ẽ ượ ọ (u,v). T nh khái ni m b c, đ i v i đ th có h ự ư ươ ra(vào) c a m t đ nh. ủ ộ ỉ
+(v)(deg-(v)).
Ta g i bán b c ra (vào) c a đ nh v trong đ th có h ng là s ủ ỉ ồ ị ậ ọ ướ ố
Đ nh nghĩa 4. ị cung c a đ th đi ra kh i nó (đi vào nó) và kí hi u la deg ủ ồ ị ệ ỏ
a b c
e d Hình 2. Đ th có h ng G ồ ị ướ
Thí d 3. ụ Xét đ th cho trong hình 2. Ta có ồ ị
deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e)=2. deg+(a)=3, deg+(b)=1 deg+(c)=1, deg+(d)=2, deg+(e)=2
Do m i cung (u,v) s đ c tính m t l n trong bán b c vào c a đ nh v và ỗ ủ ỉ ậ ộ ầ m t l n trong bán b c ra c a đ nh u nên ta có ẽ ượ ủ ỉ ộ ầ ậ
V
v ˛
V
Đ nh lý 2. Gi ng , khi đó ị ướ s G=(V,E) là đò th có h ả ử ị ∑deg+(v)= ∑deg-(v)=|E| v ˛
http://vuson.tk - Trang 6 -
Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
ấ ề ủ ướ ơ ế
ậ ng thu đ ng t ướ ề ườ ng trên các cung c a đ th . Đ th vô h ủ ồ ị ồ ị đ th vô h ng trên các cung đ c g i là ồ ị ượ ọ ng trên các ng không ph thu c vào h ộ ụ ng h p s thu n ti n h n n u ta b qua ỏ ệ c b ng cách b qua ỏ ượ ằ ướ ng ươ ứ v i đ th có h ng ng ớ ồ ị ợ ẽ ướ ướ R t nhi u tính ch t c a đ th có h ấ ủ ồ ị cung c a nó. Vì v y, trong nhi u tr ậ h ướ h ướ đã cho.
I.1.3. Đ nh nghĩa đ ng đi, chu trình , đ th liên thông. ị ườ ồ ị
đ nh u đ n đ nh v, trong đó n là s nguyên ừ ỉ ế ộ ỉ ố đ dài n t ng G=(V,E) là dãy Đ nh nghĩa 1. ị d ươ
Đ ng đi ườ ng, trên đ th vô h ướ ồ ị xo, x1 , ... , xn-1 , xn trong đó u=x0 , v=xn , ( xi , xi+1 ) ˛ E , i= 0, 1, 2 ,..., n-1.
Đ ng đi nói trên còn có th bi u di n d i d ng các c nh: ể ể ễ ướ ạ ườ ạ
(x0 , x1 ) , ( x1 , x2), ... , ( xn-1 , xn ). ọ ỉ ọ ố ủ ườ ỉ ng đi. Đ ng đi có ườ chu trình. Đ ng đi hay ườ ứ ầ ố Đ nh u g i là đ nh đ u, còn đ nh v g i là đ nh cu i c a đ ầ ỉ đ nh đ u trùng v i đ nh cu i ( t c là u=v) ớ ỉ ỉ c g i là chu trình đ i. ỉ c g i là đ ượ ọ đ nơ n u nh không có c nh nào b l p l ạ ượ ọ ị ặ ạ ư ế
ng cho trong hình 1: a,d,c,f,e là đ ồ ị ng đi đ n đ dài ơ ướ ng đi do (e,c) không ph i là c nh c a đ th . Dãy ả ườ ủ ồ ị ạ ộ Đ ng đi a,b,e,d,a,b có đ dài là 5 không ph i là ộ ả ộ ng đi đ n, do c nh (a,b) có m t trong nó hai l n. ạ ơ ườ ặ ầ Thí d 1. ụ Trên đ th vô h 4. Còn d,e,c,a không là đ ườ b,c,f,e,b là chu trình đ dài 4. đ ườ
a b c a b c
d e f
f d e Hình 1. Đ ng đi trên đ th ồ ị ườ
ng đi và chu trình trên đ th có h c đ nh nghĩa hoàn toàn ồ ị ướ ượ ị ng h p đ th vô h ng đ ng, ch khác là ta chú ý đ n h ng trên ườ ệ nh tr ự ư ườ ồ ị ợ ướ ế ướ ỉ Khái ni m đ t ng t ươ các cung.
đ nh u đ n đ nh v, trong đó n là s nguyên ừ ỉ ế ố ỉ t ộ ng G=(V,A) là dãy ướ Đ nh nghĩa 2. Đ ng đi đ dài n ườ ị ng, trên đ th có h d ồ ị ươ xo, x1 , ... , xn-1 , xn
A , i= 0, 1, 2 ,..., n-1. trong đó u=x0 , v=xn , ( xi , xi+1 ) ˛
http://vuson.tk - Trang 7 -
Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
Đ ng đi nói trên còn có th bi u di n d i d ng các cung: ể ể ễ ướ ạ ườ (x0 , x1 ) , ( x1 , x2), ... , ( xn-1 , xn ).
ỉ ọ ố ủ ườ ọ ỉ c g i là ứ ầ ố Đ nh u g i là đ nh đ u, còn đ nh v g i là đ nh cu i c a đ ầ ỉ đ nh đ u trùng v i đ nh cu i ( t c là u=v) ớ ỉ ỉ c g i là chu trình đ i. ỉ đ ượ ọ đ nơ n u nh không có cung nào b l p l ng đi. Đ ng đi có ườ chu trình. Đ ng đi hay ườ ị ặ ạ ượ ọ ư ế
Đ ng đi a,b,e,d,a,b có đ dài là 5 không ph i là
ng cho trong hình 1: a,d,c,f,e là đ ồ ị ng đi đ n đ dài ơ ộ ườ ủ ồ ị ộ ướ ng đi do (e,c) không ph i là cung c a đ th . Dãy ả ả ộ ng đi đ n, do cung (a,b) có m t trong nó hai l n. Thí d 2. ụ Trên đ th có h 4. Còn d,e,c,a không là đ ườ b,c,f,e,b là chu trình đ dài 4. đ ườ ơ ầ ườ ặ ộ ạ ấ ạ ể ự ế Xét m t m ng máy tính .M t câu h i đ t ra là hai máy tính b t kỳ trong ỏ ặ c thông tin v i nhau ho c tr c ti p qua kênh n i ố ổ ượ ặ ớ ặ ộ ạ ợ ồ ị ể ể ễ ạ ỉ ng ng v i các kênh n i) câu h i đó đ ươ ứ ạ ớ i hay chăng đ ế ử ủ ồ ị ươ ng ượ c ỏ ọ ng đi gi a m i ữ ố ườ ồ ạ ớ ể ộ m ng này có th trao đ i đ chúng h ăc thông qua m t ho c vài máy tính trung gian trong m ng? N u s d ng đ th đ bi u di n m ng máy tính này (trong đó các đ nh c a đ th t ụ ng v i các máy tính , còn các c nh t ứ phát bi u trong ngôn ng đ th nh sau: T n t ữ ồ ị ư c p đ nh c a đ th ? ặ ủ ồ ị ỉ
ng G=(V,E) đ c g i là liên thông n u luôn tìm ượ ọ ế Đ th vô h ồ ị ữ ướ ng đi gi a hai đ nh b t kỳ c a nó. ỉ ấ cv i nhau ượ ớ ể ổ ấ ng ng v i m ng này là đ th liên thông. ồ ị ươ ứ ỉ ồ ị ồ ị ồ ị Đ ng nghĩa 3. ị c đ đ ủ ượ ườ Nh v y hai máy tính b t kỳ trong m ng có th trao đ i thông tin đ ạ ư ậ khi và ch khi đ th t ạ ớ Thí d 3. ụ Trong hình 2: Đ th G là liên thông, đ th H là không liên thông a b H1
c
d e
H2
1,H2,H3.
g f H3 G H
Hình 2. Đ th liên thông G và đ th H g m 3 thành ph n liên thông H ồ ị ồ ị ầ ồ
Ta g i đ th con c a đ th G=(V,E) là đ th H=(W,F), trong đó ủ ồ ị ọ ồ ị ồ ị Đ nh nghĩa 4. ị V và F ˝ E W ˝
http://vuson.tk - Trang 8 -
Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
ườ ồ ị ộ ố ồ ị ư ậ ẽ ồ ị ợ ộ ữ ỉ c a đ th ng h p đ th là không liên thông , nó s rã ra thành m t s đ th con Trong tr liên thông đôi m t không có đ nh chung. Nh ng đ th con liên thông nh v y ta s g i là ẽ ọ các thành ph n liên thông ầ ủ ồ ị.
H1,H2,H3. Thí d 4. ụ Đ th H trong hình 2 g m 3 thành ph n liên thông là ồ ị ầ ồ
ự ỏ ữ ữ ố ể ế ạ ổ c đ a ra trong đ nh nghĩa sau. ng ng v i tình hu ng này đ Trong m ng máy tính có th có nh ng máy ( nh ng kênh n i ) mà s h ng hóc ạ c a nó có th nh h ủ t ươ ứ ệ ng đ n vi c trao đ i thông tin trong m ng. Các khái ni m ưở ị ố ệ ượ ư ể ả ớ
c g i là ị ượ ọ ế ệ
Đ nh v đ ỉ ộ ớ c g i là ầ ỏ ồ ị ỏ ồ ị ế ượ ọ ạ ỏ ệ ố ớ n u vi c lo i b v cùng v i Đ nh nghĩa 5. đ nh r nhánh ạ ỏ ẽ ỉ các c nh liên thu c v i nó kh i đ th làm tăng s thành ph n liên thông c a đ ủ ồ ạ ố th . C nh e đ c uầ n u vi c lo i b nó kh i đ th làm tăng s thành ị ạ ph n liên thông c a đ th . ủ ồ ị ầ
ồ ị ở hình 2, đ nh d và e là đ nh r nhánh, còn các c nh (d,g) ẽ ạ ỉ ỉ Thí d 5.ụ trong đ th G và (e,f) là c u.ầ Đ i v i đ th có h ng có hai khái ni m liên thông ph thu c vào vi c ta ướ ụ ệ ệ ộ có xét đ n h ng trên các cung hay không. ố ớ ồ ị ế ướ
c g i là liên thông m nh n u luôn ồ ị ướ ượ ọ ế ạ Đ nh nghĩa 6. ị c đ tìm đ ượ ườ Đ th có h ng G=(V,A) đ ng đi gi a hai đ nh b t kỳ c a nó. ủ ấ ỉ ữ
ng G=(V,A) đ c g i là liên thông y u n u đ th ồ ị ượ ọ ế ế ồ ị Đ nh nghĩa 7. ị vô h ng t Đ th có h ướ ng ng v i nó là đ th vô h ng liên thông. ướ ồ ị ươ ứ ớ ướ
ồ ị ư ế Rõ ràng n u đ th là liên thông m nh thì nó cũng là liên thông y u, nh ng đi u ề ng ế i là không luôn đúng , nh ch ra trong thí d d i đây. ạ ư ỉ c l ượ ạ ụ ướ
ạ ồ ị ạ Thí d 6. ụ Trong hình 3 đ th G là liên thông m nh, còn H là liên thông y u ế nh ng không là liên thông m nh ư b a a b
e e c d c d
Hình 3. Đ th liên thông m nh G Đ th liên thông y u H ồ ị ồ ị ạ ế
http://vuson.tk - Trang 9 -
Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
ỏ ặ ể ị ng các c nh c a m t đ th vô ủ
ộ ồ ị ng liên thông m nh? Ta ạ i đây cho ta tiêu ể ướ ồ ị t m t đ th có là đ nh h ướ c hay không. M t câu h i đ t ra là khi nào có th đ nh h ộ ng liên thông đ có th thu đ h ượ ể ướ s g i đ th nh v y là đ th đ nh h ẽ ọ ồ ị ư ậ ị chu n nh n bi ậ ạ ướ c m t đ th có h ướ ộ ồ ị c. Đ nh lý d ng đ ượ ị ng đ ượ ướ ộ ồ ị ế ẩ ị
ng liên thông là đ nh h Đ th vô h ng đ ướ ướ ượ ỗ c khi và ch khi m i ỉ Đ nh lý 1. ị ị c nh c a nó n m trên ít nh t m t chu trình. ạ ồ ị ằ ủ ấ ộ
ủ ồ ị ừ ự ồ ạ i s (u,v) là m t c nh c a đ th ,t ộ ạ c l ượ ạ ả ử ệ ầ u đ n v và ng ế ừ s t n t ấ i suy ra (u,v) ph i n m trên ít nh t ả ằ
ướ ủ ồ ị ể ạ ng liên thông m nh.Gi ng các c nh c a đ th đ thu s C là m t chu trình nào đó trong đ ủ ụ ướ ạ ướ ồ ế ng đi vòng theo nó. N u ướ ớ ỉ ư ị ng. Theo gi ị ị ộ ướ ượ ủ ọ ng). Th t c trên s đ i các c nh đã có h ng c a C’ theo m t h ạ ủ ụ ng. Khi đó ta thu đ ướ c đ nh h ẽ ượ ặ c l p ượ c ủ ồ ị ượ ị ướ ng liên thông m nh Ch ng minh. Đi u ki n c n. Gi ề ứ đ ng t ng đi có h ườ ướ m t chu trình. ộ Đi u ki n đ . Th t c sau đây cho phép đ nh h ị ệ ủ ề đ c đ th có h ượ ồ ị ả ử ộ th . Đ nh h ng các c nh trên chu trình này theo m t h ị ị ộ ướ ạ t t các c nh c a đ th là đã đ c l c đ nh h ượ ạ i , ng thì k t thúc th t c. Ng ạ ấ ủ ụ ượ ị ế ủ ồ ị ch n C là m t c nh ch a đ nh h ng có chung đ nh v i ít nh t m t trong s các ộ ạ ị ố ộ ấ ướ t tìm đ c nh đã đ nh h thi c chu trình C ch a c nh e. Đ nh ứ ạ ế ả ướ ạ c đ nh h h ng d c theo chu ng các c nh ch a đ ư ượ ị ướ ạ ướ ng l trình này( không đ nh h ạ ướ ị l i cho đ n khi t t c các c nh c a đ th đ ạ ạ ấ ả ế đ th có h ồ ị ướ ạ
I.2 Các khái ni m m đ u v đ tài c n đ c p t ở ầ ề ề i ầ ề ậ ớ ệ
˛ E c a nó đ ủ
I.2.1 M đ u ở ầ Trong ph n này chúng ta ch xét đ th có h ỉ ướ ố ồ ị ỗ ng G=(V,E) và |V|=n,|E|=m ượ ặ c đ t ầ ượ ẽ ặ ố ủ ¥ , n u (u,v) c gán tr ng s , nghĩa là , m i cung (u,v) v i các cung đ ọ ớ ng ng v i m t s th c a(u,v) g i là tr ng s c a nó.Chúng ta s đ t a(u,v)= t ớ ọ ọ ộ ố ự ươ ứ ˇ E .N u dãy ế ế ng đi trên G, thì đ dài c a nó đ v0, v1 , ... , vp là m t đ ộ ườ ủ ộ ượ c đ nh nghĩa là t ng sau: ị
i=1
ổ p ∑a(vi-1, vi)
ủ ườ ọ ủ ố ng đi chính là t ng ọ ấ ả ế các tr ng s trên các cung c a nó. t c các cung đ u b ng 1, thì ta thu ề ằ c đ nh nghĩa đ dài đu ng đi nh là s cung c a đ ng đi. t c là , đ dài c a đ ộ ứ (Chú ý r ng n u chúng ta gán tr ng s cho t ằ đ ượ ị ổ ố ư ộ ờ ố ủ ườ
ắ ồ ị ướ ạ ổ Bài toán tìm đ phát bi u d ng đi ng n nh t trên đ th d ấ ườ i d ng t ng quát nh sau : Tìm đ i d ng t ng quát có th đ ng đi có đ dài nh nh t t ể ướ ạ ư ổ ể ượ c ỏ ấ ừ ộ ườ
http://vuson.tk - Trang 10 -
Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ
ố ư ậ ẽ ọ ng đi ng n nh t t ệ ấ ắ ấ ừ ế còn đ dài c a nó s kí hi u ị ¥ s đ n t thì ta đ t d(s,t)= ặ ể ế ườ ẽ ả ừ ỉ ế s đ n t ả ư ng,thì trong đ ng đi t ươ ư ậ ế (kho ng cách đ nh nghĩa nh v y ấ ng đi ng n nh t ắ ng đi c b n đ ườ ơ ả ). ườ ặ ọ ể ữ ỉ
ả ằ ữ ấ ỉ ườ ợ ờ ứ ề ơ i đ c h t c n chú ý r ng n u bi Tr ế ng h p riêng. ườ ế ộ ằ ườ ợ ng đi ng h p tr ng s không âm, có th tìm m t cách t) ợ s đ n t, thì đ ể ˛ V tuỳ ý (s „ ả ố ố ớ ặ ỉ ầ ỉ s đ n t, trong tr ườ c đ nh v sao cho:
˛ V. Đ ng đi nh v y s g i là ˛ V đ n đ nh cu i (đích) t m t đ nh xu t phát s ộ ỉ đ ộ ủ ườ s đ n t là d(s,t) và còn g i ọ là kho ng cách t ừ có th là s âm ).N u nh không t n t i đ ố ồ ạ ườ ế đó ta th y chu trình trong đ th có đ dài d t ấ ồ ị ộ ừ i(đ không có đ nh nào l p l ng đi nh th g i là ư ế ọ ặ ạ ườ ỉ chu trình âm) thì M t khác,n u trong đ th có chu trình v i đ dài âm(g i là ớ ộ ồ ị ế ở kho ng cách gi a 1 s c p đ nh nào đó c a đ th có th là không xác đ nh, b i ị ủ ồ ị ố ặ ườ vì, b ng cách đi vòng theo chu trình này m t s đ l n l n, ta có th ch ra đ ng ể ỉ ộ ố ủ ớ ầ c nào. Trong đi gi a các đ nh này có đ dài nh h n b t kì s th c cho tr ướ ố ự ỏ ơ ộ ng đi c b n ng n nh t, tuy tru ng h p nh v y , có th đ t v n đ tìm đ ư ậ ấ ắ ơ ả ề ể ặ ấ nhiên bài toán đ t ra s tr nên ph c t p h n r t nhi u, b i vì nó ch a bài toán ơ ấ ặ ở ẽ ở ứ ạ ng đi Hamint n trong đ th nh là m t tr xét s t n t ồ ị ư ộ ườ ự ồ ạ ườ t kho ng cách t ế ầ ừ ế ướ ng n nh t t ấ ừ ọ ế ắ Đ tìm đ d dàng. ng đi , ch c n chú ý là đ i v i c p đ nh s,t ể ễ luôn tìm đ ượ ỉ
d(s,t) = d(s,v) + a(v,t) c đ nh t trong đ ỉ ướ ỉ ườ ắ ế ượ ể ủ đ nh s.Rõ ràng dãy thu đ c xác đ nh đ ng đin ng n nh t ấ ừ ả c u sao cho d(s,v)=d(s,u)+a(u,v),... T gi t v tính không âm c a các tr ng s d dàng suy ra r ng dãy t,v,u... không ằ ố ễ ng đi ượ ườ ị Th c v y đ nh v nh v y chính là đ nh đi tr ự ậ ỉ ư ậ s đ n t..Ti p theo ta có th tìm đ t ế ừ thi ọ ế ề ch a đ nh l p l ứ ỉ ở ỉ ng n nh t t ắ i và k t thúc ế ặ ạ s đ n t. ế ấ ừ
˛ V,ta tính c n trên d[v] c a kho ng cách t
ấ ấ ừ ộ ỉ ườ Ph n l n các thu t toán tìm kho ng cách gi a hai đ nh s và t đ ậ ượ I.2.2 Đ ng đi ng n nh t xu t phát t ắ ả ể ậ ˛ s đ n t ỉ đ i th nh sau: t ể ư ừ ế ấ ả ủ ậ c xây ma tr n tr ng ọ ừ ậ t c các đ nh v ỉ m t đ nh ữ ầ ớ d ng nh k thu t tính toán mà ta có th mô t ả ạ ờ ỹ ự s a[u,v],u,v ả ố V.M i khi phát hi n ệ ỗ
(1)
t lên : d[v]=d[u]+a[u,v]. c n trên d[v] s đ
ậ Quá trình đó s k t thúc khi nào chúng ta không làm t d[u]+a[u,v] ể ệ ỹ
c g i là nhãn c a đ nh v,còn vi c tính l
ủ ỉ ậ
ẽ ọ ộ ủ ụ ẽ
i các c n trên này s g i là phép gán
ạ
ọ ậ ấ
ng g i là th t c gán nhãn. Nh n th y
i c a đ th .Hi n nay ế ấ ả ừ
t thu t toán nào cho phép tìm đ ữ ậ
ườ
ủ ụ
t c các đ nh còn l
ỉ
ạ ủ ồ ị ệ
ng đi ng n nh t gi a hai đ nh làm
ắ
ườ
m t đ nh ấ
ng đi ng n nh t t
ắ ỉ
ấ ừ ộ ỉ ườ ữ ậ i. còn ch a là xác đ nh, b i vì còn ph i ch ừ ả ả ị ỉ
ả
ch n này có nh ư
ề ệ c b t c
ượ ấ ứ
c n trên nào.Khi đó, rõ ràng giá tr c a m i d[v] s cho ta kho ng cách t
ừ ỗ
m i
ị ủ
ậ
đ nh s đ n v. Khi th hi n k thu t tính toán này trên máy tính, c n trên d[v] s
ậ
ế
ỉ
đ
ệ
ượ ọ
nhãn cho đ th và toàn b th t c th
ồ ị
r ng đ tính kho ng cách t
s đ n t
ả
ể
ằ
v n ch a bi
ậ
ế
ư
ẫ
vi c th c s hi u qu h n nh ng thu t toán tìm đ
ự ự ệ
ả ơ
ệ
t c các đ nh còn l
đ n t
ạ
ỉ
ế ấ ả
S đ tính toán mà ta v a mô t
ở
ơ ồ
ch n các đ nh u và v đ ki m tra đi u ki n (1).Th t
ể ể
ứ ự ọ
ứ ự ọ
ỉ
ng r t l n đ n hi u qu thu t toán.
ậ
ệ
ấ ớ ra th t
h
ưở ế ả http://vuson.tk - Trang 11 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ ậ ậ ợ ụ ụ ể ườ ọ
ng h p ma tr n tr ng ợ ố ọ ề
đ nh s đ n các đ nh còn ỉ ế ế ậ
ấ ừ ỉ ậ ườ
ệ ơ ấ
ỉ ng h p tr ng s trên các cung là không âm thu t toán do Dijkstra đ
ng đi ng n nh t t
i quy t bài toán tìm đ
ắ
ệ ữ
ớ
ề
ơ ở ủ ạ ờ ế ậ ủ ộ ườ ế ậ
ỗ ỉ
ẽ
s đ n nó. Các nhãn này s
ờ
c l p có m t nhãn t m th i ấ ừ
ộ ướ ặ ạ ộ t c n trên c a đ dài đ
c bi nd i theo th t c l p, mà
ủ ụ ặ
ở ỗ
ế ổ
ủ
ế ẽ ở ố ị
ế
đ nh s đ n ng đi ng n nh t t
ắ ấ ừ ỉ ườ ộ nh sau:
ư ˛ V. ng G=(V,E) v i n đ nh, ầ ớ ỉ
˛ V, ma tr n tr ng s ;
ố
ậ ọ thi đ nh s đ n t i d[v],v I.2.3 Thu t toán Dijkstra_Bài toán ví d c th (tr
s không âm)
ố
Trong tr
ườ
ngh đ gi
ị ể ả
i c a đ th làm vi c h u hi u h n r t nhi u so v i thu t toán khác. Thu t toán
l
ạ ủ ồ ị
đ
c xây d ng trên c s hán cho các đ nh các nhãn t m th i. Nhãn c a m i đ nh
ự
ượ
ng đi ng n nh t t
cho bi
ắ
m i m t b
đ
ượ
tr thành nhãn c đ nh .N u nhãn c a m t đ nh nào đó tr thành c đ nh thì nó s
ố ị
ộ ỉ
ở
cho ta không ph i là c n trên mà là đ dài đ
ả
ậ
nó.Thu t toán đ
c mô t
ậ
ả
ượ
Procedure Dijkstra;
ướ
ồ ị
ỉ
t : a[u,v]
ả (*Đ u vào : Đ th có h
s˛ V là đ nh xu t phát, a[u,v]
ấ
‡ 0, u,v˛ V
ế
ừ ỉ t c các đ nh còn l
ỉ ế ấ ả ạ Gi
ả
Đ u ra : kho ng cách t
ầ
*)
Begin(*kh i t o*)
ở ạ
For v˛ V. do
Begin d[v]:=a[s, v];
Truoc [v]:=s; ạ ậ ờ ỉ ˛ T}; „ do End;
d[s]:=0;T:=V\{s};(* T là t p các đ nh có nhãn t m th i *)
(*B c l p*)
ướ ặ
While T ˘
Begin ỏ
ố ị Tim dinh u˛ T th a mãn d[u]=min {d[z]:z
T:=T\{u};(*c đ nh nhãn c a đ nh u*)
ủ ỉ
For v˛ T do (*gán nhãn l
i cho csc đ nh trong T*)
ỉ
ạ
If d[v]>d[u]+a[u,v] then
Begin d[v]:=d[u]+a[u,v]; truoc[v]:=u;
end; end;
end; ng đi có đ dài ng n nh t trên đ th sau ị ậ ườ ồ ị ắ ấ ộ Đ nh lý 1.
nhãn th i gian c O(n Thu t toán Dijkstra tìm đ
2). ờ ỡ http://vuson.tk - Trang 12 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ đ nh s đ n các đ nh còn l ỉ ấ ừ ỉ ộ ế
ố ị ằ ở ẽ ứ ng đi ng n nh t t
ắ c tìm đ
ườ
m t b
ở ộ ướ ặ
ế c nhãn c đ nh thì d(u*) chính là d dài ọ ế ượ ố ị ậ i c a
ạ ủ
ng đi ng n nh t t
ắ
c l p nào đó các nhãn c đ nh cho ta đ dài các
s đ n các đinh có nhãn c đ nh,ta s ch ng minh r ng
ấ ừ
ố ị
ế
ỉ
s đén u*.
ấ ừ
ỉ ờ ạ
ọ ố ị
ỗ ướ ặ ỉ ằ ậ
ạ
ậ
s đ n v ch qua nh ng đ nh n m hoàn toàn trong t p ằ ấ ế
ng di ng n nh t t
ắ
ủ ậ ỉ ng đi này.Do tr ng s trên các cung là không âm , nên đo n đ ng t ữ
ứ
ú đ n u* không n m tron trong t p S1, t c
ế
ọ ˛ S2 là đ nh đ u tiên nh v y trên
ầ
ế
s đ n
ạ ườ ậ
ư ậ
ừ ọ ẫ ỉ ỉ ớ
ng đin ng n nh t t
ắ ọ
ấ ẳ
ờ ả ằ ị
ế ỏ ọ ủ ầ ộ ỉ ườ ỉ
s đên v v i m i v
ớ ầ
ọ ỉ ự ự ệ ầ
2).
c l p , v y th i gian tính toán c a thu t toán là c O(n Ch ng minh.
Tr
ướ
ứ
s r ng
đ th .Gi
ồ ị ả ử ằ
đ
ườ
l n l p ti p theo n u đ nh u* thu đ
ầ ặ
đ
ng đi ng n nh t t
ườ
ắ
ờ ở
Kí hi u S1 là t p các đ nh có nhãn c đ nh, S2 là t p các đ nh có nhãn t m th i
ỉ
ệ
c l p đang xét.K t thúc m i b
b
ủ
c l p nhãn t m th i d(v)cho ta đo dài c a
ế
ướ ặ
ng đi ng n nh t t
đ
ỉ
ấ ừ
ắ
ườ
s r n đ
S1.Gi
ấ ừ
ả ử ằ ườ
là nó đi qua ít nh t m t đ nh c a t p S2.G i z
ộ ỉ
đ
ố
ườ
u* cóđ dài L>0 và d(z) < d(u*) - L < d(u*).
B t đ ng th c này là mâu thu n v i cách xác đ nh đ nh u* là đ nh có nhãn t m
ạ
ứ
ậ
th i nh nh t. V y đ
s đ n u* ph i n m tr n trong t p
ậ ườ
ấ
ấ ừ
l n l p đ u tiên S1={s} và sau m i l n
S1, và vì th d[u*] là đ dài c a nó.Do
ỗ ầ
ộ
ế
ở ầ ặ
ắ
ng đi ng n
t là d(v) cho đ dài đ
l p ta ch them vào S1 m t đ nh u* nên gi
thi
ộ
ế
ả
ặ
ọ ˛ S1 là đúng v i b
c l p đ u tiên .Theo qui n p là suy
nh t t
ạ
ớ ướ ặ
ấ ừ
s đ n m i đ nh c a đ th .
ng đi ng n nh t t
ra thu t toán cho ta đ
ế
ườ
ậ
ủ ồ ị
ấ ừ
ắ
Ở m i b
s đánh giá s phép toán c n th c hi n theo thu t toán.
Bây gi
ỗ ướ ặ
c l p
ậ
ệ
ự
ầ
ố
ờ ẽ
i cũng c n th c
đ tìm ra đi m u c n th c hi n O(n) phép toán , đ gán nhãn l
ự
ể
ể
ể
ầ
ầ
ạ
ệ
ng phép toán cũng là O(n) .Thu t toán c n ph i th c hi n n-1
hi n m t s l
ả
ậ
ộ ố ượ
ệ
b
ờ
ậ
ướ ặ ủ ậ ỡ Đ nh lý đ c ch ng minh. ị ượ ứ ườ ự
ng đi ng n nh t d[v] thì đ òng đi này có th tìm d a
ư ể ấ ắ Khi đã tìm đ
vào nhãn Tr c đ dài đ
ượ ộ
˛ V.
c[v],v
ướ đ nh 1 đ n các đ nh còn l ườ ng đi ng n nh t t
ắ ấ ừ ỉ ế ỉ ạ ủ ồ ị ở
i c a đ th Thí d 1: ụ Tìm đ
hình sau: (7) 3 2 6 (5) (1) ( 1 ) (2) (1) (1) (4) 1 (2) 4 (3) 5 http://vuson.tk - Trang 13 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ i đây.Qui ả ế ướ ậ c trình bày trong b n d
ả ướ
ượ ầ ỉ K t qu tính toán theo thu t toán đ
thành 2 ph n c a nhãn theo th t
ứ ự
ủ
b
c ch n đ c đ nh nhãn
đ
ở ướ ặ
ể ố ị
ọ
ượ
c ti p theo, vì th ta đánh d u.
các b
ướ ế t
c vi
ế
ượ
c đánh d u * là đ nh
: d[v], Truoc[v]. Đ nh đ
ỉ
ấ
ổ ở
c l p đang xét , nhãn c a nó không bi n đ i
ế
ủ
ấ ế ướ ặ Đ nh 1 ¥ ¥ ¥ ¥ ¥ ỉ
0, 1
-
-
-
- Đ nh 2
ỉ
1, 1*
-
-
-
- Đ nh 3
ỉ
,1
6, 2
4, 4 *
-
- Đ nh 4
ỉ
,1
3, 2 *
-
-
- Đ nh 5
ỉ
,1
, 1
7, 4
7, 4
6, 6 * Đ nh 6
ỉ
,1
8, 2
8, 2
5, 3 *
- B c l p
Kh i t o
ở ạ
1
2
3
4
5 ế ậ
ộ ỉ ấ ừ ế ể ế
s đ n m t đ nh t nào đó thì ta có th k t B ng k t qu tính toán theo thu t toán Dijkstra
ả
ả
N u ch c n tìm đ
ng đi ng n nh t t
ườ
ế
ỉ ầ
ắ
thúc thu t toán khi tr thành có nhãn c đ nh.
ở
ậ ố ị I.2.4 Đ ng đi trong đ th không có chu trình . ồ ị ườ ườ ứ ườ
ể ủ
ớ ộ ứ ạ ợ
ự ậ ể ọ ố c h t ta ch ng minh đ nh lý sau ng h p riêng th hai c a bài toán tìm đ
ta xét tr
Bây gi
ng đi ng n nh t, mà
ấ
ắ
ờ
2), đó là đồ
i nó có th xây d ng thu t toán v i đ ph c t p tính toán O(n
đ gi
ể ả
th không có chu trình( còn tr ng s trên các cung có th là các s th c tuỳ ý ).
ị
ố ự
Tr
ướ ế ứ ị Gi ị ả ử ồ ị ủ ố ỉ
ỉ ố ừ ỉ ỗ ể
s G là đ th không có chu trình. Khi đó các đ nh c a nó có th
ế
đ nh có ch s nh h n đ n
ng t
ỏ ơ
ễ ướ ạ
i d ng ỉ ướ
ủ ỉ ố ớ ể ể Đ nh lý 2.
đánh s sao cho m i cung c a đ th ch h
ủ ồ ị
đ nh có ch s l n h n , nghĩa là m i cung c a nó có th bi u di n d
ỗ
ơ
ỉ
(v[i],v[j]), trong đó i c đánh s th a mãn đi u ki n nêu ồ ị ỉ ượ ố ỏ ề ệ T hí d 3.ụ Đ th trong hình sau có các đ nh đ
trong đ nh lý.
ị 7 (3) 8 (5) t=9 (1) (1)
s=1 (2) 4 (5) 5 (4)
6 (1) (7) (10) (5) 2 (2) 3 Hình .Đ th không có chu trình ồ ị http://vuson.tk - Trang 14 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ ả ố ỏ
thu t toán sau, cho phép tìm ra cách đánh s th a ậ Đ ch ng minh đ nh lý ta mô t
mãn đi u kiênk đ nh lý. ể ứ
ề ị
ị ướ ứ ớ ỉ ượ
c ˛ ng G=(V,E) v i n đ nh không ch a chu trình đ
V Procedure Numbering;
(* Đ u vào
: Đ th có h
ồ ị
ầ
cho b i danh sách k Ke(v),v
ề ở ˛ V ch s NR[u] < NR[v]. *) Đ u raầ : V i m i đ nh v
ớ ỗ ỉ ỉ ố Begin V do For v˛
V do Vao[v]:=0;
(* tinh Vao[v]=deg-(v) *)
For u˛
For v˛ Ke(u) do Vao[v]:=Vao[v] + 1; QUEUE:= ˘ ; V do v ; ˘ do For v˛
If Vao[v]=0 then QUEUE (cid:220)
Num :=0;
While QUEUE „
Begin u (cid:220)
QUEUE;
Num :=num +1; NR[u] :=num;
For v˛ Ke(u) do
Begin Vao[v]:=Vao[v] - 1;
If Vao[v]=0 then QUEUE (cid:220) v ; End;
End;
End; 1) Rõ ràng trong b c xây d ng d a trên ý t ậ ả ự ưở ấ ơ ị ằ ng r t đ n gi n sau : Rõ rang trong đ
ậ
ượ ỉ đ nh v1 n u có cung đi vào nó t ế ự
cũng tìm đ
ờ
ắ ầ ừ ỉ ừ ồ
c đ nh có bán b c vào b ng 0 ( không
v2 thì ta
i chuy n sang xét đ nh v2. N u có cung v3 đi vào v2, thì ta chuy n sang xét v3... ế ự ậ
ỉ ộ ố ữ ạ ầ ư ậ ể
ể ể
ồ ị
ế ạ ỉ ỉ ắ ầ ừ ả
ị ỉ c l p l c ti p t c cho đ n khi t ư ậ ủ ồ
ế
1.Ti p
tuỳ ý b t đ u t
ứ ự
ộ
c đánh s cùng các cung đi ra kh i
ỏ
ố
ượ
ủ ụ ượ ặ ạ
c đ th m i cũng không có chu trình, và th t c đ
i
ỉ
t c các đin h
ẽ ượ ế ụ ấ ả ế c đánh s .
ố Thu t toán đ
ượ
th không có chu trình bao gi
có cung đi vào ). Th c v y, b t đ u t
l
ạ
Do đ th là không có chu trình nên sau m t s h u h n l n chuy n nh v y ta
ph i đi đ n đ nh không có cung đi vào . Tho t tiên, tìm các đ nh nh v y c a đ
th . Rõ ràng ta có th đáng s chúng theo m t th t
ố
ể
theo, lo i b kh i đ th nh ng đ nh đã đ
ạ ỏ ỏ ồ ị ữ
chúng, ta thu đ
ượ ồ ị ớ
v i đ th m i này. Quá trình đó s đ
ớ ồ ị ớ
c a đ th đ
ủ ồ ị ượ
Chú ý: ấ ả ả ị ướ
ậ ở ạ
ủ ố ỡ c đánh s cùng v i các ủ ồ
t c các cung c a đ
c kh i t o ta ph i duy t qua t
ệ
đó ta t n c O(m) phép
th khi tính bán b c vào c a các đ nh, vì v y
ậ ở
ỉ
ố ộ
toán,trong đó m là s cung cua đ th . Ti p theo m i l n đánh s m t
ế
ồ ị
ố
đ nh, đ th c hi n viêcv lo i b đ nh đã đ
ỉ ỗ ầ
ố ạ ỏ ỉ ể ự ượ ệ ớ http://vuson.tk - Trang 15 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ ệ t c các ỉ ể ỏ
ố t c các cung này. Suy
ệ ấ ả ủ ồ ị ộ ầ ữ ấ ả
ẽ ả
ậ ể ể ể c đánh s ậ
ự ậ cung đi ra kh i nó , chúng ta s ph i duy t qua t
ẽ ả
ra đ đánh s all các đ nh c đ th chúng ta s ph duy t t
ủ ồ ị
cung c a đ th m t l n n a. V y đ ph c t p thu t toán la O(m).
ậ
2) Thu t toán có th đ ki m tra xem đ th có ch a chu trình hay không?
ố ư ượ ứ
ỉ ˛ V. Th c v y, n u k t thúc thu t toán v n còn có đ nh ch a đ
ậ
(num ˛ E ta có i ], i=1,2,...,n ở
v[1] đ n t c ghi trong t c các đ nh còn l
ỉ ừ Đ u raầ i đ
ạ ượ : Đ th G=(V,E) trong đó V= { v[1], v[2], ..., v[n] }
Đ i v i m i cung (v[i],v[j])
ố ớ
ỗ
Đ th đ
c cho b i danh sách k Ke(v),v
ồ ị ượ
: Kho ng cách t
ả
* ) m ng d[v[i] ả Begin d[v[1] ]:=0; for j:=2 to n do d[v[j] ]:=a[v[1] ],v[j] ];
fo j:=2 to n do for v˛ Ke [v [j ] ] do
d [v ]:=min ( d [v ], d [v [j ] ] + a [v [j ] ], v ); ỗ ậ ủ ồ ị ả ụ ả ở t là ả ệ ữ ự ươ ự
ớ ng đ
ể trên th
ườ
ề ấ ữ ấ ả ỉ ng đi ng n nh t gi a t ặ ỉ ặ
ắ t c các c p đ nh
ấ
ườ
ả ở ụ ậ ủ ồ ị ậ ặ ặ ồ ị ố ợ ổ
t nh t . ầ t c các că pđ nh
ữ ấ ả
ẽ
c, trong đó ta s
ướ
c thu t toán v i
ớ
ượ
3) đ i v i tr
ợ
ng h p
ố ớ ườ
ng h p t ng quát ,
ườ
đây ta
ấ Ở
ố
3) : thu t toán Floyd, tt đ
ượ
c ả
thu t toán v i đ ph c t p tính toán O(n
ớ ộ ứ ạ ậ ả
ả ư end;
Đ ph c t p c a thu t toán là O(m)., do m i cung c a đ th ph i xét qua đúng
ộ ứ ạ ủ
m t l n.
ộ ầ
ừ
c ng d ng vào vi c xây d ng nh n
Các thu t toán mô t
ệ
ượ ứ
ậ
ph
i bài toán đi u khi n vi c th c hi n nh ng d án l n, g i t
ng pháp gi
ọ ắ
ự
ệ
PERT (Project Evaluation and Review Technique ) hqy CMD ( Critical path
method)
I.2.5 Đ ng đi ng n nh t gi a t
ắ
ườ
i bài toán tìm đ
Rõ ràng ta có th gi
ể ả
m c tr
c a đ th b ng cách s d ng n l n thu t toán mô t
ử ụ
ủ ồ ị ằ
ầ
t là các đ nh c a đ th .Rõ ràng , khi đó ta thu đ
ch n s l n l
ỉ
ầ ượ
ọ
4) (n u dùng tt Ford-Bellman) ho c O(n
đ ph c t p là O(n
ế
ộ ứ ạ
tr ng s không âm ho c đ th không có chu trình. Trong tr
ọ
s d ng thu t toán Ford-Bellman n l n không ph i là cách làm t
ậ
ử ụ
s mô t
ậ
ẽ
nh sau
mô t
Procedure Floyd;
(* Tìm đ ng đi ng n nh t gi a t t c các c p đ nh
ấ ữ ấ ả ặ ỉ ườ ắ http://vuson.tk - Trang 16 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ : Đ th cho b i ma tr n tr ng s a[i,j], i,j=1,2,...,n ồ ị ở
ng đi ng n nh t gi a các c p đ nh Đ u vào
ầ
Đ u raầ ậ
ắ ố
ữ ọ
ấ ặ ỉ ậ ườ : Ma tr n đ
d[i,j] i,j =1,2,...,n ườ ng di ng n nh t t
ắ ấ ừ i đ n j.
ế trong đó d[i,j] cho đ dài đ
ng đi
Ma tr n ghi nh n đ ộ
ậ ườ ậ c j trong đ ậ ỉ ướ ườ ấ
ng đi ng n nh t
ắ p[i,j], i, j=1,2,...,n.
trong đó p[i,j] ghi nh n đ nh đi tr
ừ ế .
i đ n j
t *)
Begin (* Kh i t o *)
ở ạ For i:=1 to n do For j:=1 to n do
Begin d[i,j]:=a[i,j];
p[i,j]:=i; end; (* B c l p *)
ướ ặ
For k:=1 to n do For i:=1 to n do For j:=1 to n do
If d[i,j] > d[i,k] + d[k,j] then
Begin d[i,j]:= d[i,k] + d[k,j ];
p [i,j ]:= p [k,j ]; end; 3). end;
Rõ ràng đ ph c t p c a thu t toán là O(n ộ ứ ạ ủ ậ Ch ng II ươ : GI I THU T_ ậ ề ể ể ố ủ ọ ồ ị
ả ể ắ
ng đi ng n
ộ
ườ
si n u i k s, d[j] =+ ∞
ề ế ng đi ng n nh t gi a m t c p đ nh. II.1 Phân tích.
Dùng ma tr n k đ bi u di n đ th C= (cij), cij = tr ng s c a cung (i,j), cij
ễ
=+ ∞ n u không có cung (i,j). M t m ng d[] đ ghi các đ dài đ
ế
ộ
nh t t
s t
i đ nh i đang có . Xu t phát d[s] =0 và d[i] =c
ấ ừ ớ ỉ
ấ
n u j không k s.
ề
ế
ậ tìm đ
i thu t
II.2 Gi
ả ấ ữ ộ ặ ườ ắ ỉ nghĩa 1.0. Đ nh
ị R Xét đ th có tr ng s c nh
ồ ị ố ạ G = (V,E,w), v i hàm tr ng s ọ ớ ọ ố w:Efi là ánh x t t p các c nh E đ n t p s th c ạ ừ ậ ạ ế ậ ố ự R. http://vuson.tk - Trang 17 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ Đ ng đi p t đ nh u đ n đ nh Đ nh nghĩa 1.1.
ị ườ ừ ỉ ế ỉ ố
v là dãy các c nh n i ạ ti p nhau b t đ u t đ nh u k t thúc t i đ nh p t ắ ầ ừ ỉ ế ế ạ ỉ v. Đ ng đi
ườ ừ u đ n ế v đ ượ ể
c bi u di n nh sau: p=(u=v0,v1…,vk=v) ư ễ Đ dài c a đ ng đi Đ nh nghĩa 1.2.
ị ủ ườ ộ p = ( v0,v1,...,vk ), ký hi uệ w (p), k (
vw , v ) ng đi: là t ng các tr ng s c a các c nh trên đ
ố ủ ạ ọ ổ ườ i i 1 =
1 i - w (p) = (cid:229) t c đ ng đi t Đ nh nghĩa 1.3.
ị G i ọ ˆ (u,v) là t p t ậ ấ ả ườ ừ u đ n ế v. Đ dài ộ w đ đ nh u đ n đ nh v đ ườ ng đi ng n nh t
ắ ấ t ừ ỉ ế ỉ ượ c xác đ nh b i:
ị ở ({min p |) p )},(
vu ˆ ˛ d(u,v) = Đ ng đi ng n nh t đ nh u đ n đ nh v là ườ ấ pmin(u,v) t ắ ừ ỉ ế ỉ ng đi có đ dài d(u,v). Đ nh nghĩa 1.4.
ị
đ
ộ
ườ II.3 Gi i thu t Dijkstra. ả ậ
II.3.1 N i dung
ộ Có r t nhi u gi i bài toán tìm đ ề ấ ả i thu t đã đ
ậ ượ c phát tri n đ gi
ể ể ả ườ ắ
ng đi ng n nh t gi a m t c p đ nh, trong khuôn kh bài vi t này em ch xin gi ộ ặ ữ ấ ổ ỉ ế ỉ ớ i thi u gi
ệ ả
i thu t Dijkstra. Gi i thu t Dijkstra là m t gi i thu t đ gi i bài toán đ ng đi ậ ả ậ ộ ả ậ ể ả ườ ng n nh t ngu n đ n trên m t đ th có tr ng s c nh mà t t c các tr ng s ộ ồ ị ố ạ ắ ấ ồ ơ ọ ấ ả ọ ố ng đi ng n nh t gi a hai đ nh cho tr đ nh đ u không âm. Nó xác đ nh đ
ề ị ườ ữ ấ ắ ỉ c, t
ướ ừ ỉ b. a đ n đ nh
ế ỉ m i đ nh v, gi i thu t Dijkstra xác đ nh 3 thông tin: kv, dv và pv. Ở ỗ ỉ ả ậ ị v. kv: mang giá tr boolean xác đ nh tr ng thái đ
ị ạ ị ượ c ch n c a đ nh
ọ ủ ỉ t c các đ nh v ch a đ c ch n, nghĩa là: ầ ở ạ ấ ả ỉ ư ượ ọ Ban đ u ta kh i t o t
kv = false, " v ˛ V. ng đi mà ta tìm th y cho đ n th i đi m đang d v: là chi u dài đ ề ườ ể ế ấ ờ xét t ừ a đ n ế v. Kh i t o, V \{a}, da = 0. ở ạ dv = ¥ , " v ˛ http://vuson.tk - Trang 18 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ c c a đ nh v trên đ p v: là đ nh tr ỉ ướ ủ ỉ ườ ng đi ng n nh t t
ắ ấ ừ a đ n ế b. Đ ng đi ng n nh t t {a,...,pv,v,...,b}. Kh i t o, ấ ừ a đ n ế b có d ng ạ ườ ắ ở ạ pv = null, " v˛ V. Sau đây là các b c c a gi i thu t Dijkstra: ướ ủ ả ậ V; dv:= ¥ ," v ˛ V \ {a}, da:=0. B1. Kh i t o: Đ t
ở ạ ặ kv:= false " v ˛ B2. V sao cho kv = false và dv = min {dt / t˛ V, kt = false} Ch n ọ v ˛ , không t n t ng đi t N u ế dv = ¥ thì k t thúc
ế i đ
ồ ạ ườ ừ a đ n ế b. B3. Đánh d u đ nh v, kv:= true. ấ ỉ và db là đ dài đ B4. N u ế v = b thì k t thúc ế ộ ườ ng đi ng n nh t t
ắ ấ ừ a đ nế b. Ng i n u c l ượ ạ ế v „ b sang B5. u k v i B5. V i m i đ nh
ớ ỗ ỉ ề ớ v mà ku = false, ki m tra ể N u ế du > dv + w(v,u) thì du:= dv + w(v,u) Ghi nh đ nh v: pu:= v.Quay l ớ ỉ i ạ B2. II.3.2 Đ ph c t p c a gi .
i thu t Dijkstra ộ ứ ạ ủ ả ậ *** Tr ườ ng h p s d ng ma tr n k .
ậ ề ợ ử ụ i thu t Dijkstra kh o sát m t c nh c a đ th G i ọ f(n) là s l n gi ố ầ ả ủ ồ ị G trong ộ ạ ả ậ tr ườ ng h p x u nh t. Khi đó ta có:
ấ ợ ấ f(n) < O(|V|2) Cho n = |V|, B5 là vòng l p ch a các b Ch ng minh:
ứ ứ ặ ướ B2 fi
c B5, vòng l pặ đ v = b.Vì m i vòng l p ta rút ra m t đ nh c a ượ c th c hi n đ n khi
ệ ự ế ở ỗ ộ ỉ ủ V và kh iở ặ , nên vòng l p đ đ u ầ V có n ph n t ầ ử ặ ượ ử c x lý nhi u nh t là
ề ấ n l n.ầ i đa đ c kh o sát là Ở B2 s đ nh t ố ỉ ố ượ ả n - 1 đ nhỉ i đa đ Ở B5 s đ nh k t
ố ỉ ề ố ả n -1 đ nhỉ Do đó: c kh o sát là
ượ
f(n) £ 2(n-1)n < O(|V|2) V y đ ph c t p c a gi i thu t Dijkstra là O(|V|2). ộ ứ ạ ủ ậ ả ậ http://vuson.tk - Trang 19 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ *** Tr ng h p s d ng danh sách k ườ ợ ử ụ ề Đ ph c t p c a gi i thu t Dijkstra là O((|V| + |E|)lg|V|). ộ ứ ạ ủ ả ậ t toán Dijstra ậ II.3.3 L u đư Begin n, C = (c ), a, z
ij L(a) = 0
L(v) = v a
T(i) = 1 i n S z T Đ T sao cho L[v] đ t min ạ Ch n v
ọ
T = T \ {v} S x T & k về Đ L(x) = min(L(x), L(v) + c(v,x)) L(z) End http://vuson.tk - Trang 20 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ II.3.4 B ng d li u ch y thô.
ữ ệ ả ạ T o ma tr n nh sau
ậ ư ạ 6
0 4 2 0 0 0
4 0 1 5 0 0
2 1 0 8 10 0
0 5 8 0 2 6
0 0 10 2 0 3
0 0 0 6 3 0 ồ ị ư a d Ta có đ th nh sau
b 5 c
4 6
1 8
2
10 3 e f B ng ch y thô ả ạ V T b e c f d ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ a
0
* ¥ 2*
* ¥ 4
3*
* 10
8*
* bcdef
bcfd
cfd
fd
d 12
12
12*
* a
e
b
c
f
d 14
15
* a đ dài t
ộ ừ f là 15 http://vuson.tk - Trang 21 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ Ch ng III : ươ ề ấ ừ ỉ ươ ườ đ nh S đ n đ nh T theo
ế ỉ ng trình tìm đ
Đ tài : Ch
thu t toán Dijkstra _S d ng ngôn ng l p trình C
ử ụ ng đi ng n nh t t
ắ
ữ ậ ậ #include #define m 50
int C[m][m],DD[m],L[m],T[m]; int n;
void inmatran(char *st,int C[m][m])
{
cout<<"\n\n"< }
} void docfile(char *st)
{
FILE*f;
int t;
f=fopen(st,"rt");
if(f!=NULL)
{
fscanf(f,"%d",&n);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
{
fscanf(f,"%d",&t);
C[i][j]=t;
}
fclose(f);
} }
void Dijkstra(int a,int z) http://vuson.tk - Trang 22 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ {
for(int i=1;i<=n;i++)
{ L[i]=1000;
T[i]=1;
DD[i]=0; }
L[a]=0;
while(T[z]==1)
{ for(int v=1;v<=n;v++) if(T[v]==1 && L[v]!=1000) break; for(int j=v+1;j<=n;j++) if(T[j]==1 && L[j] T[v]=0;
for(int x=1;x<=n;x++) if(T[x]==1 && C[v][x]!=0)
if(L[x]> (L[v]+C[v][x]))
{ L[x]=L[v]+C[v][x];
DD[x]=v; } }
}
void duongdi(int a,int z)
{
cout<<"\n\n\tDo dai duong di ngan nhat : "< {
printf("%d <-- ",z);
z=DD[z];
} cout< ẫ ủ ườ ị ụ ể void main()
{
clrscr();
docfile("d:\\ok\\dacs\\matran.dnc"); //chú ý đ
ậ
ng d n c a ma tr n
cout<<"\n\n*** TIM minPath() BANG THUAT TOAN DIJKSTRA. ***";
Dijkstra(a,z); // thay 1 giá tr c th
duongdi(a,z); // thay 1 giá tr c th
ị ụ ể http://vuson.tk - Trang 23 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ getch(); } *****K t lu n****** ế ậ t h n v bài toán tìm đ ắ ọ ắ ố ơ ề ườ
ng ữ ậ ấ ẫ ề Tóm l
i, thông qua môn h c này giúp em n m b t t
ạ
đi ng n nh t gi a hai đ nh thông qua thu t toán Dijkstra.
ỉ
ắ
Tuân theo các nguyên t c mà th y h
ắ
sót trong quá trình hoàn thành đ án c s này, ầ ướ
ồ ơ ở ng d n đ ra, tuy nhiên v n còn nhi u sai
ẫ
mong th y giúp đ nhi u h n....
ỡ ề
ề ơ ầ ả *****
ứ ả : Nguy n Đ c Nghĩa, Nguy n Tô Thành_NXB Giáo D c
ụ
ễ ******Tài li u tham kh o
ệ
Toán r i r c_tác gi
ễ
ờ ạ ế ể ủ ướ ầ ướ ng d n***
ẫ ***Nh n xét, h
ng phát tri n, ý ki n đánh giá c a th y h
ậ
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
................................................................................................................................. .....
.......................................................................................................................................
............................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
................................................................................................................................. .....
.......................................................................................................................................
............................................................................................................................ ..........
.......................................................................................................................................
.......................................................................................................................
.......................................................................................................................................
................................................................................................................................. http://vuson.tk - Trang 24 - Đ án c s ơ ở ồ GVHD: Đoàn Văn Th ng ắ .......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
................................................................................................................................. .....
.......................................................................................................................................
............................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
................................................................................................................................. .....
.......................................................................................................................................
............................................................................................................................ ..........
.......................................................................................................................................
....................................................................................................................... ...............
.......................................................................................................................................
..................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
.................................................................................................................................
.......................................................................................................................................
................................................................................................................................. http://vuson.tk - Trang 25 -Ậ L U Đ THU T TOÁN DIJKSTRA
Ậ
Ư Ồ
Ả
thuồ
NG TRÌNH
CÀI Đ T CH
Ặ
ƯƠ
