ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
Ờ
Ầ
L I NÓI Đ U
ừ
ệ ề ấ ự ơ ả ủ ế ồ ị ữ lâu đ ivà có nhi u c đ xu t ờ ứ ng c b n c a lý thuy t đ th đ
ạ ầ ủ ế ồ ị ươ ề ụ i Th y Sĩ
ườ ử ụ ổ ế ọ ỗ ạ i l c ng ồ ị ể ả ườ i bài toán n i ti ng ở i đã s d ng đ th đ gi
ầ ở thàng ph Konigsberg.
ự ể ả ồ ị ượ ử ụ ố c s d ng đ gi
ể ộ Lý thuy t đ th là m t lĩnh v c nghiên c u đã có t ứ ụ ư ưở 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 t Leonhard Euler.Chính ông là ng ề v các cái c u Đ th đ ẳ
ề ả ồ ị ệ ệ
ớ i tích m ch đi n.Chúng ta có th phân bi ứ nh ng khác nhau v c u trúc phân t
ể ể ị
Đ ồ
ồ ị ủ
ể ả ư ọ
ờ ể ử ụ ố ạ ấ
ề ậ ị ử ụ ể ờ ộ ng đi ng n nh t gi a hai thành ph trong cùng m t m ng giao thông . Chúng ố i các bài toán v l p l ch,th i khoá bi u,và phân b
ữ ồ ị ể ả ạ
ơ ả ụ ể ằ
ủ ứ ư ụ
ữ ậ ấ
ượ ướ ớ ế ề i quy t các bài toán trong nhi u lĩnh v c ạ ị ể ử ụ ạ khác nhau .Ch ng h n , đ th có th s d ng đ xác đ nh các m ch vòng trong ọ ữ ể ấ ạ ấ ợ v n đ gi t các h p ch t hoá h c h u ử ử ư ơ ề ấ c khác nhau v i cùng công th c phân t ổ ờ ồ ị ạ nh đ th .Chúng ta có th xác đ nh xem hai máy tính trong m ng có th trao đ i ạ ượ ớ thông tin đ c v i nhau hay không nh mô hình đ th c a m ng máy tính. ạ ị ố th có tr ng s trên các c nh có th s d ng đ gi i các bài toán nh : tìm ắ ườ đ ta còn s d ng đ th đ gi ề ầ ố t n s cho 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 ệ ế t cùng v i vi c phân tích và h c trình bày chi ti
ươ ệ ệ 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 ể ả ế ấ i quy t nh t , bài toán tìm đ ặ ẫ ng d n cài đ t chúng đã đ 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
ệ ng trình trên 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.
ễ ế 1
SVTH : Nguy n Công Hi u_SBD 0041 Trang
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
ươ
Ế
ƯỜ
Ch ng I :
NG ĐI
Ậ Ấ
Ề Ắ
LÝ THUY T V THU T TOÁN TÌM Đ 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 ố ệ t các lo i đ th khác nhau b i ki u và s ượ ạ c t i
ể ả
ả ử ạ ụ ử ụ ồ s ta có m t m ng g m các máy tính và các
ố
ạ ố ạ ở
ạ ạ ể các đ 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 ộ ạ ộ m t m ng máy tính .Gi kênh ệ ể ể ạ ọ ắ t là tên tho i) n i các máy tính này.Chúng ta có th bi u đi n tho i(g i t ị ở ể ặ ễ 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
Huế An Giang
ộ ị 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
ấ ỳ
ậ ấ ấ ằ ộ ỉ ạ ả ạ
i đ
ượ ọ ị ồ ị đ n đ th vô h ng ạ ề ữ 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 ơ ồ ạ ạ ượ ố ớ c n i v i chính nó.S đ m ng máy tính cho và không có máy tính nào l ế ướ => ta đi đ n đ nh nghĩa sau: ơ tronh hình 1 đ c g i là
ị ơ ậ ồ ỉ ng G=(V,E) bao g m V là t p đ nh,và E là t p . Đ n đ th vô h
ồ ị ứ ự ồ ầ ử ủ ạ ậ ọ Đ nh nghĩa 1 ặ các c p không có th t ướ g m hai ph n t khác nhau c a V g i là các c nh.
ễ ế 2
SVTH : Nguy n Công Hi u_SBD 0041 Trang
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
ả ề i nhi u
ề ả ng xuyên ph i truy n t ớ ạ ữ ả ố ườ ề ạ ợ i ta ph i n i hai máy này b i nhi u kênh tho i . M ng v i đa
ng h p gi a hai máy tính nào đó th ườ ữ ượ ạ ườ Trong tr thông tin ng kênh tho i gi a các máy tính đ ở c cho trong hình 2.
ồ ế Hà Tây Đ ng Nai Hu An Giang
ộ Hà N i HCM Bình Đ nhị
Quãng Ngãi
Phú Yên
ơ ồ ạ Khánh Hòa ớ ạ Hình 2. S đ m ng máy tính v i đa kênh tho i
ướ ồ ỉ ng G=(V,E) bao g m V là t p các đ nh , và E là ồ ị . Đa đ th vô h
ứ ự ồ ầ ử ọ ậ ủ khác nhau c a V g i là các
ượ ọ ươ ứ ạ ớ g m hai ph n t ặ ế c g i là c nh l pn u chúng cùng t ng ng v i
ỉ ị Đ nh nghĩa 2 ặ ọ h các c p không có th t ạ ạ c nh .Hai c nh e 1 va e2 đ ộ ặ m t c p đ 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.
ễ ế 3
SVTH : Nguy n Công Hi u_SBD 0041 Trang
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
ồ ị ỗ ơ ồ ị ề
ư ề ồ ị ồ ị ồ ị ộ ặ ơ ạ ả ố ỉ
ạ ữ ộ
ể ụ ạ
ớ c cho trong ở ẳ ư ậ ể ạ ả ượ đ
ớ ồ ị ố ườ ữ ạ
ng h p này chúng ta ư ả ồ ị ượ ị ướ ệ 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 đ ư ậ hình 3.Nh v y đa đ th không th mô t c m ng nh v y, b i vì có ộ ỉ nh ng khuyên (c nh n i m t đ nh vói chính nó).Trong tr ế ầ ử ụ c n s d ng đ n khái ni m gi ợ c đ nh nghĩa nh sau: đ th vô h 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)
g m hai ph n t ượ ọ ặ ọ ế ạ ả ồ ị ị đ 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).
ạ ạ ề
ạ ừ ể ậ ộ ỉ
ẳ ươ ộ ố
ế ở ướ ượ ề ạ ả ộ các máy ỉ 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 ề ượ c chi u c thay th b i hai c nh có h ể ỉ Hà N i ch có th nh n tin t ạ ng ng
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 ủ ở ề chi u.Ch ng h n trong hình 4 máy ch ể ử ở ị đ a ph ề 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:
ễ ế 4
SVTH : Nguy n Công Hi u_SBD 0041 Trang
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
ướ ậ ỉ
ồ ủ ọ ị Đ 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.
ế ả ử ụ ề ẽ ế ộ
ạ ồ ị ể ướ ng: ạ 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
ướ ồ ỉ
ngG=(V,E) bao g m V là t p các đ nh,và E là ầ ử g m hai ph n t ậ ọ khác nhau c a V g i là các cung.Hai
ươ ứ ộ ặ ặ ớ ỉ ồ ị Đa đ th có h ứ ự ồ ng ng v i cùng m t c p đ nh đ ủ ượ ọ c g i là cung l p. ị Đ nh nghĩa 5. ặ ọ h các c p có th t cung e1 va e2 t
ơ ể ủ ế ậ ệ ớ ơ ẽ ỏ ắ ọ ồ ị ẽ ng.Vì v y, đ cho ng n g n , ta s b qua tính t ướ ng ỗ đ n m i
ữ ơ ả
ẽ ậ 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
ế ồ ị ướ ướ ế ầ 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 ụ thuy t đ th .Tr ng. vô h
ỉ ị ủ ồ ị ượ ọ ướ ế
Hai đ nh u va v c a đ th có h ạ ế ủ ồ ị ng G đ ủ ồ ị ạ
ố ỉ ạ ỉ ỉ
ẽ ượ ọ ầ ủ ạ ờ ỉ ề 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 đ c g i là các đ nh đ u c a c nh (u,v).
ể ể ế ộ ỉ ư ạ ị ộ ớ t có bao nhiêu c nh liên thu c v i m t đ nh , ta đ a vào đ nh
Đ có th bi nghĩa 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ó
ồ ị deg(a)=1, deg(b)=4 , deg(c)=4 , deg(f)=3, deg(d)=1 ,
ễ ế 5
SVTH : Nguy n Công Hi u_SBD 0041 Trang
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
ậ ượ ọ ụ ỉ ỉ đ nh treo deg(e)=3 , deg(g)=0. ỉ cô l pậ , đ nh b c 1 đ ọ .Trong ví d trên
c g i là ậ ủ ỉ ấ ậ ỉ ậ ỉ Đ 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 :
ị ả ử ướ ớ ồ ị . Gi ạ ng v i m c nh . Khi đó Đ nh lý 1
s G=(V,E) là đ th vô h 2m=∑ deg(v) v (cid:0) V
ứ ỗ ạ ượ ộ ầ c tính m t l n trong deg(u)
Rõ ràng trong m i c nh e=(u,v) đ ấ ả ừ ổ ậ ủ ằ ỉ t c các b c c a các đ nh b ng hai
Ch ng minh. ộ ầ và m t l n trong deg(v). T đó suy ra t ng t ầ ố ạ l n 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
ướ ậ ẻ ố ẻ ố ỉ ậ ộ ồ ị 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.
ứ ự ậ ọ ươ ứ ậ ẻ ỉ ậ ỉ . Th c v y, g i O và U t ậ ng ng là t p đ nh b c l và t p đ nh
U
ủ ồ ị Ch ng minh ẵ ậ b c ch n c a đ th ,ta có
v (cid:0) ỉ
V ẵ ớ
2m=∑deg(v)= ∑deg(v)+ ∑deg(v) v (cid:0) ổ
ứ ậ ủ ả ở ậ ẻ ế ỉ ổ
ả ồ
ổ ố ẵ
O v (cid:0) trên là Do deg(v) là ch nv i v là đ nh trong U nên t ng th hai trong v ph i ổ ừ ố ẵ s 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 , nên t ng này ph i g m ả ậ ẻ ố ỉ ộ ố ẵ 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.
ứ ấ ố ạ ậ ữ ươ ố ạ ậ Ta xét các thu t ng t ng t
ị ế ỉ
ướ ng G thì ta nói hai đ nh u và ặ ẽ ượ ọ ủ ố ỉ ỉ
ố ớ ồ ị ươ ướ ệ ệ ậ ậ ng ta có khái ni m bán b c
ộ ỉ ủ ồ ị N u e=(u,v) là cung c a đ th có h Đ 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 Đinh u (v) s đ cung (u,v). ự ư ng t T nh khái ni m b c, đ i v i đ th có h ủ ra(vào) c a m t đ nh.
ọ ậ ủ ỉ ồ ị ướ Ta g i bán b c ra (vào) c a đ nh v trong đ th có h ố ng là s
ễ ế 6
ị Đ nh nghĩa 4. cung SVTH : Nguy n Công Hi u_SBD 0041 Trang
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
+(v)(deg(v)).
ệ ỏ ủ ồ ị 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ó
ị ướ Gi ng , khi đó Đ nh lý 2.
V
v (cid:0)
V
ị ả ử s G=(V,E) là đò th có h ∑deg+(v)= ∑deg(v)=|E| v (cid:0)
ấ
ề ủ
ề ủ ồ ị ượ ọ ợ ẽ ướ ướ ướ ụ ộ ng không ph thu c vào h ng trên các ỏ ế ơ ệ ng h p s thu n ti n h n n u ta b qua ượ ằ ỏ c b ng cách b qua ớ ồ ị ng ng ậ ng thu đ ng t c g i là ươ ứ v i đ th có
ấ ủ ồ ị 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 ướ h ướ ườ ồ ị ng trên các cung c a đ th . Đ th vô h ồ ị đ th vô h ng trên các cung đ ng đã 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
ị Đ nh nghĩa 1. ươ d đ dài n t ng G=(V,E) là dãy
ườ Đ ng đi ướ ồ ị ng, trên đ th vô h xo, x1 , ... , xn1 , xn trong đó u=x0 , v=xn , ( xi , xi+1 ) (cid:0) E , i= 0, 1, 2 ,..., n1.
ể ể ễ ướ ạ ườ ạ Đ 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), ... , ( xn1 , xn ). ọ ỉ ỉ ọ ố ủ ườ
ầ ứ ố ườ ng đi. Đ ng đi có ườ chu trình. Đ ng đi hay
ị ặ ạ ư ế i. ỉ ượ ọ c g i là đ ạ đ nơ n u nh không có c nh nào b l p l
ế 7
ầ ỉ Đ 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 đ ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
ướ ồ ị ườ
ng cho trong hình 1: a,d,c,f,e là đ ạ
ộ ộ ơ ng đi đ n đ ủ ồ ị ả
ạ ơ ườ ả 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 dài 4. Còn d,e,c,a không là đ b,c,f,e,b là chu trình đ dài 4. ườ đ
c a b c a b
f d e
e f d ồ ị ườ 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
ồ ị ợ ướ ế ướ ỉ ệ ườ ự ư ườ nh tr ng h p đ th vô h ồ ị ng đ ng, ch khác là ta chú ý đ n h ng trên
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 , ... , xn1 , xn
trong đó u=x0 , v=xn , ( xi , xi+1 ) (cid:0) A , i= 0, 1, 2 ,..., n1.
ể ể ễ ướ ạ ườ Đ 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), ... , ( xn1 , xn ).
ỉ ọ ố ủ ườ ọ ỉ
ứ ầ ố c g i là ườ 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. ỉ ượ ọ đ đ nơ n u nh không có cung nào b l p l
ướ ồ ị ườ ng cho trong hình 1: a,d,c,f,e là đ
ộ ộ ơ ng đi đ n đ ủ ồ ị ả
ơ ầ ng đi đ n, do cung (a,b) có m t trong nó hai l n. Thí d 2. ụ Trên đ th có h dài 4. Còn d,e,c,a không là đ b,c,f,e,b là chu trình đ dài 4. ườ đ
ườ ả ng đi do (e,c) không ph i là cung c a đ th . Dãy ườ ộ Đ ng đi a,b,e,d,a,b có đ dài là 5 không ph i là ặ ộ ấ ỳ ạ
ạ ể ự ế
ỏ ặ 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 máy tính , còn các c nh t
ế ễ
ộ ố 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 ỏ ố ạ ươ ứ ng ng v i các kênh n i) câu h i t SVTH : Nguy n Công Hi u_SBD 0041 Trang 8
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
ượ ữ ồ ị ư ồ ạ ườ i hay chăng đ ng đi
c phát bi u trong ngôn ng đ th nh sau: T n t ọ ặ ủ ồ ị ể đó đ ỉ ữ gi a m i c p đ nh c a đ th ?
ượ ọ ế c g i là liên thông n u luôn tìm
ồ ị Đ th vô h ữ
ượ ớ ể cv i
ướ ỉ ng đi gi a hai đ nh b t k c a nó. ấ ỳ ồ ị ươ ứ ổ ồ ị ạ ỉ
ng ng v i m ng này là đ th liên thông. ồ ị ồ ị
ị ng G=(V,E) đ Đ 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 đ ớ nhau 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
g f
H3
G H
1,H2,H3.
ồ ị ầ ồ ồ ị 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 (cid:0) E W (cid:0)
ườ ồ ị
ộ ố ồ ị ư ậ ẽ ồ ị ợ ộ ữ ỉ
Trong tr ng h p đ th là không liên thông , nó s rã ra thành m t s đ th con liên thông đôi m t không có đ nh chung. Nh ng đ th con liên thông nh v y ta ủ ồ ị. ẽ ọ c a đ th s g i là ầ các thành ph n liên thông
ồ ị ầ ồ Thí d 4. ụ Đ th H trong hình 2 g m 3 thành ph n liên thông là H1,H2,H3.
ự ỏ ữ ữ ố
ể ế ạ ổ
ệ ượ ư ể ả ớ ạ 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 ệ ưở ủ ng đ n vi c trao đ i thông tin trong m ng. Các khái ni m c a nó có th nh h ị ố ươ ứ t c đ a ra trong đ nh nghĩa sau. ng ng v i tình hu ng này đ
ị ượ ọ ế ệ c g i là
ỉ Đ nh v đ ộ ớ ỏ ồ ị ầ ạ ạ ỏ ẽ ỉ n u vi c lo i b v cùng v i đ nh r nhánh Đ nh nghĩa 5. ố 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 đ ớ ủ ồ
ế ễ 9
SVTH : Nguy n Công Hi u_SBD 0041 Trang
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
ỏ ồ ị ạ ỏ ệ ế ố ượ ọ c g i là c uầ n u vi c lo i b nó kh i đ th làm tăng s thành
ị ạ ầ ủ ồ ị th . C nh e đ 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
Thí d 5.ụ trong đ th G (d,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
ố ớ ồ ị ế ướ ệ ng trên các cung hay không. ta có xét đ n h
ồ ị ướ ượ ọ ế ạ c g i là liên thông m nh n u luôn
ữ ị Đ nh nghĩa 6. ượ ườ c đ tìm đ ng G=(V,A) đ Đ th có h ấ ỳ ủ ỉ 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 ượ ạ c l i đây.
ế ạ
ồ ị ạ
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
ỏ ặ ể ị ủ 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
ạ ướ c. Đ nh lý d ượ ộ ồ ị ế ẩ ị ộ 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 ể ướ ồ ị t m t đ th có là đ nh h ướ ộ ồ ị c m t đ th có h ị ượ ng đ ướ ng đ ướ c hay không.
ướ ượ ướ ỗ Đ th vô h ng liên thông là đ nh h ỉ c khi và ch khi m i ng đ
ủ ộ
ồ ị ằ ễ ấ ế
ị ị Đ nh lý 1. ạ c nh c a nó n m trên ít nh t m t chu trình. SVTH : Nguy n Công Hi u_SBD 0041 Trang 10
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
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 các c nh c a đ th đ thu
ạ ng liên thông m nh.Gi s C là m t chu trình nào đó trong
ị ạ
ủ ồ ị ướ ng thì k t thúc th t c. Ng ng đi vòng theo nó. c
ỉ
ướ ượ
ạ ướ
t tìm đ ủ ng c a C’ theo m t h ướ ế ướ ạ ị ng l
ủ ồ ị ượ ị ạ ủ ụ ộ ướ ộ ướ ng các c nh trên chu trình này theo m t h ủ ụ ế ượ c đ nh h ộ ấ ớ ng có chung đ nh v i ít nh t m t trong ứ ạ c chu trình C ch a c nh e. ộ ướ ọ ng d c theo ẽ ủ ụ ng). Th t c trên s ướ c đ nh h ạ ng các c nh ch a đ ướ i các c nh đã có h ấ ả t c các c nh c a đ th đ ng. Khi đó ta
ướ ạ ề ứ 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 ượ ị ạ ế ấ t các c nh c a đ th là đã đ N u t ộ ạ ạ ướ ư ị ị i , ch n C là m t c nh ch a đ nh h l ả ị ố thi ng. Theo gi s các c nh đã đ nh h ư ượ ị ị Đ nh h c đ nh h ạ chu trình này( không đ nh h ế ượ ặ ạ c l p l đ i cho đ n khi t ượ ồ ị c đ th có h thu đ ng liên thông m nh
ở ầ ề ề ầ ề ậ ớ ệ I.2 Các khái ni m m đ u v đ tài c n đ c p t i
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
(cid:0) E c a nó đ ủ
ầ ượ ố ồ ị ỗ ượ ặ c đ t
ẽ ặ ố ủ ọ 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
ớ v i các cung đ ớ ươ ứ t a(u,v)= (cid:0) ế , n u (u,v)
ộ ườ ủ ộ ọ c gán tr ng s , nghĩa là , m i cung (u,v) ộ ố ự ọ (cid:0) E .N u dãy ế v0, v1 , ... , vp là m t đ ng đi trên G, thì đ dài c a nó đ ượ c
ị đ nh nghĩa là t ng sau:
i=1
ổ p ∑a(vi1, vi)
ủ ườ ủ ổ ố
ọ các tr ng s trên các cung c a ấ ả ế ằ ọ
ng đi chính là t ng ố ư ằ ượ ị ủ ườ ộ ờ ộ ứ t c là , đ dài c a đ nó.(Chú ý r ng n u chúng ta gán tr ng s cho t ố thu đ c đ nh nghĩa đ dài đu ng đi nh là s cung c a đ ề t c các cung đ u b ng 1, thì ta ng đi.
ổ ắ ồ ị ướ ạ
ộ ỏ
ố ể ượ i d ng t ng quát có th đ c ườ ấ ừ ng đi có đ dài nh nh t t (cid:0) V. Đ ng đi nh v y s g i là ư ậ ẽ ọ
ể ướ ạ ấ ắ ng đi ng n nh t t
ấ ừ ế còn đ dài c a nó s kí hi u ị (cid:0) ấ ườ ng đi ng n nh t trên đ th d ư ổ i d ng t ng quát nh sau : Tìm đ (cid:0) V đ n đ nh cu i (đích) t ế ỉ ủ ộ s đ n t s đ n t ồ ạ ườ ể
i đ ộ ố ấ
ả ư đó ta th y chu trình trong đ th có đ dài d ấ ồ ị ặ ạ ườ ườ ẽ ả ừ ng đi t s đ n t thì ta đ t d(s,t)= ươ ng,thì trong đ ườ ư ế ọ ỉ Bài toán tìm đ phát bi u d ộ ỉ m t đ nh xu t phát s ườ đ 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 ừ t nh t không có đ nh nào l p l i(đ ệ ư ậ ừ ế (kho ng cách đ nh nghĩa nh v y ặ ế ườ ắ ng đi ng n ơ ả ). ng đi c b n ng đi nh th g i là đ
ễ ế
SVTH : Nguy n Công Hi u_SBD 0041 Trang 11
ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ
ặ ế
ỉ ữ ồ ị ố ặ ớ ộ ủ ồ ị ọ ể
ộ ố ủ ớ ầ
ố ự ữ
ả ằ ộ ng đi gi a các đ nh này có đ dài nh h n b t kì s th c cho tr ể ặ ấ ỏ ơ ề ườ ờ ợ
ơ ả ở
ự ồ ạ ườ ồ ị ề ư ườ ộ ẽ ở ng đi Hamint n trong đ th nh là m t tr ỉ ư ậ ặ i đ
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 ướ ấ ườ c nào. đ ấ ắ Trong tru ng h p nh v y , có th đ t v n đ tìm đ ng đi c b n ng n nh t, ứ ơ ấ ứ ạ tuy 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 ợ ơ ng h p toán xét s t n t riêng.
ế ừ ế ế Tr c h t c n chú ý r ng n u bi
ằ ườ ườ ộ ợ s đ n t, trong tr (cid:0) ườ ả ố ố ớ ặ ỉ ầ ỉ t kho ng cách t ọ ng đi , ch c n chú ý là đ i v i c p đ nh s,t ng đi ng h p tr ng s không âm, có th tìm m t cách t) s đ n t, thì đ ể (cid:0) V tu ý (s ỳ
ế ầ ướ ế ấ ừ ắ ng n nh t t ể ễ Đ tìm đ d dàng. ượ ỉ luôn tìm đ c đ nh v sao cho:
d(s,t) = d(s,v) + a(v,t) ỉ ườ ỉ c đ nh t trong đ
ể ế
ủ
ượ ỉ ị ắ ỉ ướ ậ ng đin ng n ế c u sao cho d(s,v)=d(s,u)+a(u,v),... s đ n t..Ti p theo ta có th tìm đ ọ ằ ố ễ ế ề thi 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... ở ỉ ứ c xác đ nh đ nh s.Rõ ràng dãy thu đ ế i và k t thúc
ự ư ậ Th c v y đ nh v nh v y chính là đ nh đi tr ượ ấ ừ nh t t ừ ả T gi ặ ạ không ch a đ nh l p l ấ ừ ườ đ ắ ng đi ng n nh t t ế s đ n t.
ấ ấ
ậ ượ ườ Ph n l n các thu t toán tìm kho ng cách gi a hai đ nh s và t đ
ầ ớ ờ ỹ m t đ nh ữ ả ạ
ậ ả ừ ộ ỉ ắ I.2.2 Đ ng đi ng n nh t xu t phát t ỉ ả ể ư ể đ i th nh sau: t (cid:0) V,ta tính c n trên d[v] c a kho ng cách t ừ c xây ừ ậ ma tr n ế ấ ả s đ n t t c các
ậ ự d ng nh k thu t tính toán mà ta có th mô t ủ ọ tr ng s a[u,v],u,v ỉ đ nh v ố (cid:0) V.M i khi phát hi n ệ
(1)
ậ c n trên d[v] s đ t lên : d[v]=d[u]+a[u,v].
ỗ
d[u]+a[u,v] ỗ ẽ t thêm đ
ả ỹ ể ệ
ủ ỉ ậ
ẽ ọ c g i là nhãn c a đ nh v,còn vi c tính l ộ ủ ụ ậ ấ ế ấ ả ệ ng g i là th t c gán nhãn. Nh n th y
i c a đ th .Hi n nay ậ
ườ
ủ ụ
ạ ủ ồ ị
ỉ
t c các đ nh còn l
ữ
ắ
ỉ
ấ
ườ
ng đi ng n nh t gi a hai đ nh
ấ ừ
ắ
ườ
ng đi ng n nh t t ữ
ạ ượ ấ ứ
c b t c
ị ủ
ậ
ừ ỗ
m i
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
ẽ
ậ
ế
ỉ
đ 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
ạ
ệ
ượ ọ
i các c n trên này s g i là phép gán
đ
ọ
ồ ị
nhãn cho đ th và toàn b th t c th
ể
ả
ằ
ừ
s đ n t
r ng đ tính kho ng cách t
ế
ậ
ư
ẫ
t thu t toán nào cho phép tìm đ
v n ch a bi
ệ
ậ
ả ơ
ự ự ệ
làm 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
m t đ nh đ n t ừ ả ả ị ỉ
còn ch a là xác đ nh, b i vì còn ph i ch ư
ề ệ ch n này có ấ ớ i.
ở
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
ưở
ả
nh h ễ ế SVTH : Nguy n Công Hi u_SBD 0041 Trang
12 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ậ ậ ợ ụ ụ ể ườ ọ
ng h p ma tr n tr ng ố ọ ợ ỉ ế ế ậ
ấ ừ ỉ ườ
ơ ấ ề
ng h p tr ng s trên các cung là không âm thu t toán do Dijkstra đ
ắ
đ nh s đ n các đ nh còn
ng đi ng n nh t t
i quy t bài toán tìm đ
ề
ớ
ệ ữ
ỉ ậ
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
ủ
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 ờ
ế s đ n nó. Các nhãn ệ
ự
ơ ở
ế ậ
t c n trên c a đ dài đ
ế ổ ộ ườ
c bi nd i theo th t c l p, mà
ố ị ủ ộ
ủ ụ ặ
ế ậ
ạ
ấ ừ
ắ
ng đi ng n nh t t
ộ ướ ặ
ở ỗ
m i m t b
ộ ỉ
ủ
ộ ườ ậ
ả ậ ả
c mô t ư
nh sau: ầ ớ ng G=(V,E) v i n đ nh, ọ ỉ
(cid:0) V, ma tr n tr ng s ;
ố
ậ thi (cid:0) 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
ạ ủ ồ ị
l
ượ
toán đ
ỗ ỉ
m i đ nh cho bi
ẽ ượ
c l p có m t nhãn
này s đ
ố
ở
ờ ở
ạ
t m th i tr thành nhãn c đ nh .N u nhãn c a m t đ nh nào đó tr thành c
ấ ừ
ắ
ẽ
ị
ng đi ng n nh t t
đ nh thì nó s cho ta không ph i là c n trên mà là đ dài đ
ượ
ế
ỉ
đ nh s đ n nó.Thu t toán đ
Procedure Dijkstra;
ướ
ồ ị
ỉ
t : a[u,v]
ả (*Đ u vào : Đ th có h
s(cid:0) V là đ nh xu t phát, a[u,v]
ấ
(cid:0) 0, u,v(cid:0) V
ế
ừ ỉ ế ấ ả ạ ỉ
t c các đ nh còn l đ nh s đ n t i d[v],v ả
Gi
ầ
Đ u ra : kho ng cách t
*)
ở ạ
Begin(*kh i t o*)
For v(cid:0) V. do
Begin d[v]:=a[s, v];
Truoc [v]:=s; ạ ậ ờ ỉ (cid:0) do (cid:0) T}; 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 (cid:0)
Begin ỏ
ố ị Tim dinh u(cid:0) T th a mãn d[u]=min {d[z]:z
ủ ỉ
T:=T\{u};(*c đ nh nhãn c a đ nh u*)
For v(cid:0) 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 ờ ỡ Thu t toán Dijkstra tìm đ
2). ế ễ Đ nh lý 1.
nhãn th i gian c O(n
SVTH : Nguy n Công Hi u_SBD 0041 Trang
13 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ỉ ấ ừ ỉ i c a đ nh s đ n các đ nh còn l ộ ế
ố ị ằ ẽ ứ ườ
c tìm đ
ở ộ ướ ặ
m t b
ế ở ướ
Tr
ả ử ằ
s r ng
ắ
ng đi ng n nh t t ọ ế ượ ố ị ậ ạ ọ c l p đang xét.K t thúc m i b ế ữ ậ
ạ
ỉ ạ ủ
ắ
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
ế
ỉ
c nhãn c đ nh thì d(u*) chính là d dài
ấ ừ
s đén u*.
ỉ
ế
ấ ừ ế ậ ắ
ng đi ng n nh t t
ả ử ằ ườ
s r n đ ấ ừ
ủ ậ ườ s đ n v ch qua nh ng đ nh n m hoàn toàn trong t p
ắ
ng di ng n nh t t
ộ ỉ
ấ
ố ạ ườ ờ
ỉ
ố ị
ờ
ỗ ướ ặ
c l p nhãn t m th i d(v)cho ta đo dài
ằ
ỉ
ậ
ằ
ú đ n u* không n m tron trong t p S1,
ư ậ
ỉ
ừ
ng t ọ (cid:0) S2 là đ nh đ u tiên nh v y
ầ
s ng đi này.Do tr ng s trên các cung là không âm , nên đo n đ ẫ ỉ ỉ ỏ ọ ớ
ắ
ng đin ng n nh t t ườ ầ
ọ ỉ Ở m i b
ạ ự ậ ố ầ
s đánh giá s phép toán c n th c hi n theo thu t toán. ự ể ể
ậ ự ệ ầ ủ ồ ị
s đ n m i đ nh c a đ th .
ỗ ướ
c
ầ
ầ
i cũng c n
ng phép toán cũng là O(n) .Thu t toán c n ph i th c ướ ặ ủ ậ ờ ỡ ứ
Ch ng minh.
ồ ị
đ 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
ở ướ ặ
b
ủ ườ
c a đ
S1.Gi
ứ
t c là nó đi qua ít nh t m t đ nh c a t p S2.G i z
ọ
trên đ
ọ
ế
đ n 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
ở ầ ặ
ầ
ỗ
ộ
ế
ủ
S1, và vì th d[u*] là đ dài c a nó.Do
l n l p đ u tiên S1={s} và sau m i
ộ
ế
ả
ỉ
ầ ặ
ộ ỉ
thi
ng đi
t là d(v) cho đ dài đ
l n l p ta ch them vào S1 m t đ nh u* nên gi
ọ (cid:0) S1 là đúng v i b
ấ ừ
ạ
ớ ướ ặ
ớ
ắ
c l p đ u tiên .Theo qui n p
s đên v v i m i v
ng n nh t t
ế
ấ ừ
ắ
ườ
ậ
ng đi ng n nh t t
là suy ra thu t toán cho ta đ
ệ
ờ ẽ
Bây gi
ặ
ệ
ể
l p đ tìm ra đi m u c n th c hi n O(n) phép toán , đ gán nhãn l
ự
th c hi n m t s l
ệ
hi n n1 b ộ ố ượ
ậ
c l p , v y th i gian tính toán c a thu t toán là c O(n ả
2). ị ượ ứ Đ nh lý đ c ch ng minh. ư ể ắ ấ ng đi ng n nh t d[v] thì đ òng đi này có th tìm Khi đã tìm đ
ự
d a vào nhãn Tr ượ ộ
c đ dài đ
ướ
c[v],v ườ
(cid:0) V. ườ ấ ừ ỉ ế ỉ ắ
ng đi ng n nh t t đ nh 1 đ n các đ nh còn l ạ ủ ồ ị ở
i c a đ th Thí d 1: ụ Tìm đ
hình sau: (7) 3 2 6 (1) (5) ế ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
14 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ( 1 ) (2) (1) (1) (4) 1 (2) 4 (3) 5 ướ ặ Đ nh 1 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ỉ
Đ nh 4
,1
3, 2 *
ỉ
0, 1
ỉ
Đ nh 2
1, 1*
ỉ
Đ nh 3
,1
6, 2
4, 4 *
ỉ
Đ 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 ậ ả c trình bày trong b n d c ế
ế c đánh d u * i đây.Qui
ượ
ủ ướ
ả ướ
ấ
ỉ
: d[v], Truoc[v]. Đ nh đ
c l p đang xét , nhãn c a nó không ượ
ổ ở ế ấ ượ
K t qu tính toán theo thu t toán đ
ứ ự
ủ
ầ
t thành 2 ph n c a nhãn theo th t
vi
ở ướ ặ
ể ố ị
ọ
ỉ
b
c ch n đ c đ nh nhãn
là đ nh đ
ế
ế
ướ
c ti p theo, vì th ta đánh d u.
các b
bi n đ i ế B ng k t qu tính toán theo thu t toán Dijkstra ấ ừ ế ậ
ộ ỉ ể ế
s đ n m t đ nh t nào đó thì ta có th k t ố ị ả
ả
ế
ỉ ầ
ắ
ườ
ng đi ng n nh t t
N u ch c n tìm đ
ở
ậ
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 ợ ườ ườ ấ ta xét tr ắ
ng đi ng n nh t, ng h p riêng th hai c a bài toán tìm đ
ớ ộ ứ ạ
ể ứ
ậ ự ủ
i nó có th xây d ng thu t toán v i đ ph c t p tính toán O(n
ố ự ể ọ ướ ế ứ ị ờ
Bây gi
2), đó là
ể ả
mà đ 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 c h t ta ch ng minh đ nh lý sau ị ả ử ồ ị ủ 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 ị T hí d 3.ụ Đ th trong hình sau có các đ nh đ
ồ ị
nêu trong đ nh lý. 7 (3) 8 ễ ế SVTH : Nguy n Công Hi u_SBD 0041 Trang
15 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ (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 ị ả ậ ố
thu t toán sau, cho phép tìm ra cách đánh s ể ứ
ỏ ề ị Đ ch ng minh đ nh lý ta mô t
th a mãn đi u kiênk đ nh lý. ứ ớ ỉ ướ ng G=(V,E) v i n đ nh không ch a chu trình (cid:0) ở Procedure Numbering;
ồ ị
ầ
: Đ th có h
(* Đ u vào
ượ
đ c cho b i danh sách k Ke(v),v V (cid:0) ớ ỉ ố ề
ỗ ỉ V ch s NR[u] < NR[v]. : V i m i đ nh v *) Đ u raầ Begin V do For v(cid:0)
V do Vao[v]:=0;
(* tinh Vao[v]=deg(v) *)
For u(cid:0)
For v(cid:0) Ke(u) do Vao[v]:=Vao[v] + 1; QUEUE:= (cid:0) ; V do v ; (cid:0) do For v(cid:0)
If Vao[v]=0 then QUEUE (cid:0)
Num :=0;
While QUEUE (cid:0)
Begin u (cid:0)
QUEUE;
Num :=num +1; NR[u] :=num;
For v(cid:0) Ke(u) do
Begin Vao[v]:=Vao[v] 1;
If Vao[v]=0 then QUEUE (cid:0) v ; End;
End;
End; ậ ự ấ ơ ả c xây d ng d a trên ý t ị ằ ậ
c đ nh có bán b c vào b ng 0 ừ ế ự
ưở
ờ
cũng tìm đ
ự ậ
ỉ ể ể ế ạ ượ
Thu t toán đ
th không có chu trình bao gi
( không có cung đi vào ). Th c v y, b t đ u t
v2 thì ta l ồ
ng r t đ n gi n sau : Rõ rang trong đ
ượ ỉ
ắ ầ ừ ỉ
đ nh v1 n u có cung đi vào nó t
i chuy n sang xét đ nh v2. N u có cung v3 đi vào v2, thì ta chuy n ễ ế SVTH : Nguy n Công Hi u_SBD 0041 Trang
16 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ộ ố ữ ạ ầ ỉ ể ế ư ậ ạ
ộ ể ố ạ ỏ ượ ỉ ỏ ồ ị ữ
ượ ồ ị ớ ế ụ c ti p t c cho đ n i v i đ th m i này. Quá trình đó s đ
ố
c đánh s . ồ ị
sang xét v3... 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
tu ý
ố
ế
ắ ầ ừ
c đánh s cùng
1.Ti p theo, lo i b kh i đ th nh ng đ nh đã đ
b t đ u t
ỏ
c đ th m i cũng không có chu trình, và
các cung đi ra kh i chúng, ta thu đ
ủ ụ ượ ặ ạ ớ ồ ị ớ
ế
ẽ ượ
th t c đ
c l p l
ỉ ủ ồ ị ượ
ấ ả
t c các đin h c a đ th đ
khi t
Chú ý: 1) Rõ ràng trong b ả ệ ủ ướ ấ ả ỉ ậ ủ ố ồ ị ố ộ ỉ ệ ể ự
ỏ ể ố ỉ ấ ả
ẽ
ộ ứ ạ ủ ồ ị ộ ầ ữ ậ ậ 2) Thu t toán có th đ ki m tra xem đ th có ch a chu trình hay ở ạ
t c các cung c a
c kh i t o ta ph i duy t qua t
ố ỡ
ậ ở
ồ ị
đ th khi tính bán b c vào c a các đ nh, vì v y
đó ta t n c O(m)
ỗ ầ
ế
phép 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 đã đ
c đánh s cùng v i
ệ
ả
ẽ
t c các cung
các cung đi ra kh i nó , chúng ta s ph i duy t qua t
ệ
ả
ủ ồ ị
này. Suy ra đ đánh s all các đ nh c đ th chúng ta s ph duy t
ấ ả
t
t c các cung c a đ th m t l n n a. V y đ ph c t p thu t toán
la O(m).
ậ ồ ị ứ ể ể ể
ế
ế ự ậ ậ ỉ ư ượ
c ố ẫ
ồ ị ứ ề không? Th c v y, n u k t thúc thu t toán v n còn có đ nh ch a đ
đánh s (num ượ ủ ỉ ỉ ế
ỏ ế ố
t là các đ nh c a nó đ
ỉ ố ớ
ượ ể ả
Do có thu t toán đánh s trên, nên khi xét đ th không có chu trình ta có th gi
ừ ỉ
ỉ ố
ỗ
đ nh có ch s
thi
ồ ị
ấ
ỉ
nh đ n đ nh có ch s l n h n . Thu t toán tìm đ
ng đi ng n nh t trên đ th
không có chu trình đ ồ ị
c đánh s sao cho m i cung ch đi t
ơ
ắ
ả
c mô t ố
ậ
ườ
ơ ồ
trong s đ sau đây : Procedure Critical_Path; ườ ấ ừ ỉ ồ ế ấ ả ạ ắ
ng đi ng n nh t t đ nh ngu n đ n t ỉ
t c các đ nh còn l i trên (* Tìm đ
ồ ị
đ th không có chu trình *) (cid:0) V. (cid:0) E ta có i ầ ồ ị Đ u vào ừ ạ ượ ở
v[1] đ n t ỉ
t c các đ nh còn l i đ c ghi trong Đ u raầ ], i=1,2,...,n ả : Đ th G=(V,E) trong đó V= { v[1], v[2], ..., v[n] }
ố ớ
ỗ
Đ i v i m i cung (v[i],v[j])
ồ ị ượ
c cho b i danh sách k Ke(v),v
Đ th đ
ả
: 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(cid:0) Ke [v [j ] ] do
d [v ]:=min ( d [v ], d [v [j ] ] + a [v [j ] ], v ); end; ễ ế SVTH : Nguy n Công Hi u_SBD 0041 Trang
17 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ỗ ậ ả ủ ồ ị ụ ả ở ả ệ ữ ự ươ ự
ớ ng đ
ể ườ
trên th
ề t ỉ ấ ữ ấ ả ặ
ắ ặ ỉ ng đi ng n nh t gi a t t c các c p đ nh
ấ
ườ
ả ở ụ m c tr ầ ượ ặ 3) : thu t toán
ậ ầ ả ậ
ớ ộ ứ ạ
ậ
thu t toán v i đ ph c t p tính toán O(n
ả ư nh sau ấ ữ ấ ả ỉ ng đi ng n nh t gi a t ắ
ồ ị : Đ th cho b i ma tr n tr ng s a[i,j], i,j=1,2,...,n t c các c p đ nh
ậ
ắ ặ
ố
ữ ậ ườ ọ
ấ ặ ỉ ở
ng đi ng n nh t gi a các c p đ nh ộ ứ ạ ủ
Đ 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
ọ ắ
ự
ệ
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
ph
là PERT (Project Evaluation and Review Technique ) hqy CMD ( Critical path
method)
ắ
ườ
I.2.5 Đ ng đi ng n nh t gi a t
ữ ấ ả
ể ả
t c các că pđ nh
i bài toán tìm đ
Rõ ràng ta có th gi
ướ
ậ
ầ
ử ụ
ủ ồ ị ằ
c, trong đó ta
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 đ
s ch n s l n l
c thu t toán
3) đ i v i tr
4) (n u dùng tt FordBellman) ho c O(n
ố ớ ườ
ế
ớ ộ ứ ạ
v i đ ph c t p là O(n
ng
ợ ổ
ọ
ườ
ặ ồ ị
ố
ợ
ng h p t ng
h p tr ng s không âm ho c đ th không có chu trình. Trong tr
ấ
ố
ử ụ
t nh t .
quát , s d ng thu t toán FordBellman n l n không ph i là cách làm t
ẽ
ả
Ở
đây ta s mô t
ượ
Floyd, tt đ
c mô t
Procedure Floyd;
ườ
(* Tìm đ
ầ
Đ 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
ừ
t ế .
i đ n j *)
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 ế ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
18 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ 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] =+ ∞ i đ nh i đang có . Xu t phát d[s] =0 và d[i] =c ộ ặ ườ ắ ỉ 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 đ
ấ
ấ ừ ớ ỉ
s t
nh t t
ề
ế
n u j không k s.
ậ tìm đ
ả
i thu t
II.2 Gi ấ ữ
ng đi ng n nh t gi a m t c p đ nh. ị
Đ nh nghĩa 1.0. ồ ị ọ ớ ọ Xét đ th có tr ng s c nh ố ạ G = (V,E,w), v i hàm tr ng s ố w:E(cid:0) ạ ừ ậ ạ t p các c nh E đ n t p s th c R là ánh x t ế ậ ố ự R. ườ ừ ỉ ế ỉ ạ Đ ng đi p t đ nh u đ n đ nh ố
v là dãy các c nh n i ị
Đ nh nghĩa 1.1. ắ ầ ừ ỉ ế ế ạ ỉ ti p nhau b t đ u t đ nh u k t thúc t i đ nh ườ
v. Đ ng đi p t ừ u đ n ế v đ cượ ư ể ễ bi u di n nh sau: p=(u=v0,v1…,vk=v) ị ủ ộ ườ ng đi Đ dài c a đ p = ( v0,v1,...,vk ), ký hi uệ Đ nh nghĩa 1.2. k ố ủ ạ ọ ổ ườ (cid:0) (p), là t ng các tr ng s c a các c nh trên đ ng đi: v vw
( , ) i i 1 i 1 (cid:0) (cid:0) (p) = (cid:0) (cid:0) ậ ấ ả ườ G i ọ (cid:0) (u,v) là t p t t c đ ng đi t ừ u đ n ế v. Độ ị
Đ nh nghĩa 1.3. (cid:0) ườ ừ ỉ ế ỉ ượ ở ắ
ng đi ng n nh t dài đ ấ t đ nh u đ n đ nh v đ ị
c xác đ nh b i: p p ({min |) vu
)},( (cid:0) (cid:0) d(u,v) = ườ ắ ừ ỉ ế ỉ Đ ng đi ng n nh t ấ pmin(u,v) t đ nh u đ n đ nh v ườ ộ ị
Đ nh nghĩa 1.4.
d(u,v).
ng đi có đ dài
là đ ế ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
19 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ả II.3 Gi i thu t Dijkstra. ậ
ộ
II.3.1 N i dung ề ấ ả ượ ể ả ườ Có r t nhi u gi ậ
i thu t đã đ ể
c phát tri n đ gi i bài toán tìm đ ắ
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 ố ị ườ ữ ấ ắ ỉ ề
đ u không âm. Nó xác đ nh đ ng đi ng n nh t gi a hai đ nh cho tr ướ ừ ỉ
c, t đ nh ế ỉ a đ n đ nh b. Ở ỗ ỉ ả ậ ị m i đ nh v, gi i thu t Dijkstra xác đ nh 3 thông tin: kv, dv và pv. ạ ị ượ ị
k v: mang giá tr boolean xác đ nh tr ng thái đ ọ ủ ỉ
c ch n c a đ nh v. ầ ở ạ ấ ả ỉ ư ượ ọ t c các đ nh v ch a đ c ch n, nghĩa là: Ban đ u ta kh i t o t
kv = false, (cid:0) v (cid:0) V. ề ườ ể ế ấ ờ dv: là chi u dài đ ng đi mà ta tìm th y cho đ n th i đi m đang xét t ừ a đ n ế v. ở ạ dv = (cid:0) , (cid:0) v (cid:0) Kh i t o, V \{a}, da = 0. ỉ ướ ủ ỉ ườ p v: là đ nh tr c c a đ nh v trên đ ắ
ng đi ng n nh t t ấ ừ a đ n ế b. ườ ắ Đ ng đi ng n nh t t ấ ừ a đ n ế b có d ng ạ {a,...,pv,v,...,b}. Kh i t o, ở ạ pv = null, (cid:0) v(cid:0) V. ướ ủ ả ậ Sau đây là các b c c a gi i thu t Dijkstra: ặ kv:= false (cid:0) v (cid:0) V; dv:= (cid:0) ,(cid:0) v (cid:0) V \ {a}, da:=0. ở ạ
B1. Kh i t o: Đ t Ch n ọ v (cid:0) V sao cho kv = false và dv = min {dt / t(cid:0) V, kt = false} B2. ồ ạ ườ N u ế dv = (cid:0) ế
thì k t thúc , không t n t i đ ng đi t ừ a đ n ế b. ấ ỉ v, kv:= true. B3. Đánh d u đ nh ế ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
20 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ế ộ ườ và db là đ dài đ ắ
ng đi ng n nh t t ấ ừ a đ nế B4. N u ế v = b thì k t thúc b. Ng i n u c l ượ ạ ế v (cid:0) b sang B5. ỗ ỉ ể u k v i ề ớ v mà ku = false, ki m tra ớ
B5. V i m i đ nh 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 . ố ầ ả ộ ạ ả ậ G i ọ f(n) là s l n gi i thu t Dijkstra kh o sát m t c nh c a đ th ủ ồ ị G trong ườ ấ ợ tr ấ
ng h p x u nh t. Khi đó ta có: f(n) < O(|V|2) ứ ặ ứ
Ch ng minh: Cho n = |V|, B5 là vòng l p ch a các b ướ B2 (cid:0)
c B5, vòng ượ ự ế ở ỗ ộ ỉ ặ ặ
l p đ ệ
c th c hi n đ n khi v = b.Vì m i vòng l p ta rút ra m t đ nh c a ủ V và ầ ử ặ ượ ử ấ kh i đ u ở ầ V có n ph n t , nên vòng l p đ ề
c x lý nhi u nh t là n l n.ầ ố ỉ ố ượ ả i đa đ c kh o sát là n 1 đ nhỉ Ở B2 s đ nh t ề ố ượ ả i đa đ c kh o sát là n 1 đ nhỉ ố ỉ
Ở B5 s đ nh k t Do đó: f(n) (cid:0) 2(n1)n < O(|V|2) ộ ứ ạ ủ ậ ả ậ V y đ ph c t p c a gi i thu t Dijkstra là O(|V|2). ườ ợ ử ụ ề *** 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|). ậ II.3.3 L u đư t toán Dijstra ế ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
21 Begin ), a, z
n, C = (c
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 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ế ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
22 ơ ở ồ Đ á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 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) a
0
* (cid:0) 2*
* (cid:0) 4
3*
* 10
8*
* bcdef
bcfd
cfd
fd
d 12
12
12*
* a
e
b
c
f
d 14
15
* ộ
đ dài t ừ f là 15 a ế ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
23 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ươ Ch ng III : ề ấ ừ ỉ ươ ườ ế ỉ đ nh S đ n đ nh T theo ắ
ng đi ng n nh t t
ữ ậ ậ ng trình tìm đ
Đ tài : Ch
ử ụ
thu t toán Dijkstra _S d ng ngôn ng l p trình C #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"< cout< }
} void docfile(char *st)
{
FILE*f;
int t;
f=fopen(st,"rt");
if(f!=NULL)
{ ễ ế SVTH : Nguy n Công Hi u_SBD 0041 Trang
24 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ 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)
{
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)
{ ế ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
25 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ 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
getch(); } ế ậ *****K t lu n****** ọ ạ ề ắ i, thông qua môn h c này giúp em n m b t t t h n v bài toán tìm ắ ỉ ắ ố ơ
ậ
ề ẫ ề ng đi ng n nh t gi a hai đ nh thông qua thu t toán Dijkstra.
ầ ướ
ồ ơ ở ẫ
ỡ ề ầ ng d n đ ra, tuy nhiên v n còn nhi u sai
mong th y giúp đ nhi u Tóm l
ữ
ấ
ườ
đ
ắ
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,
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 phát tri n, ý ki n đánh giá c a th y h ẫ
ng d n*** ế
ậ
***Nh n xét, h
....................................................................................................................................
.................................................................................................................................... ế ễ SVTH : Nguy n Công Hi u_SBD 0041 Trang
26 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
.................................................................................................................................... ễ ế SVTH : Nguy n Công Hi u_SBD 0041 Trang
27 ơ ở ồ Đ án c s GVHD: Đoàn Văn Th ng ắ ....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
.................................................................................................................................... ễ ế SVTH : Nguy n Công Hi u_SBD 0041 Trang
28 Ư Ồ
Ả
Ậ
Ậ L U Đ THU T TOÁN DIJKSTRA
thuồ
ƯƠ
Ặ
CÀI Đ T CH
NG TRÌNH
