Danh sách đỀ TÀi học phầN: HỆ ĐIỀu hành và MẠng máy tính yêu cầu sinh viên thực hiện
Đề tài số 408:Xây dựng chương trình định đường phân tán
tải về 0.57 Mb. Chế độ xem pdf
|
| Đề tài số 408:Xây dựng chương trình định đường phân tán
Mét tËp ®Æc biÖt c¸c ®Ønh ®-îc x©y dùng b»ng c¸ch céng thªm mét ®Ønh trong mét b-íc lÆp (ThuËt to¸n nµy dùa trªn mét d·y c¸c b-íc lÆp.). Thñ tôc g¸n nh·n ®-îc thùc hiÖn trong mçi lÇn lÆp ®ã. Trong thñ tôc g¸n nh·n nµy, ®Ønh w ®-îc g¸n nh·n b»ng ®é dµi ®-êng ®i ng¾n nhÊt tõ a ®Õn w chØ ®i qua c¸c ®Ønh thuéc tËp ®Æc biÖt. §Ønh ®-îc thªm vµo lµ ®Ønh cã nh·n nhá nhÊt víi c¸c ®Ønh ch-a cã trong tËp ®ã. Gîi ý thuËt to¸n Dijkstra ThuËt to¸n Dijkstra ®-îc x©y dùng theo ph-¬ng ph¸p g¸n nh·n: Procedure Dijkstra (G : ®å thÞ träng sè) {G cã c¸c ®Ønh a = v 0 , v 1 ...vn = z vµ träng sè w(vi , vj), víi w(vi , vj) = nÕu {vi , vj} kh«ng lµ c¹nh trong G} Đồ án hệ điều hành và mạng máy tính 9 for i:=1 to n L(vi) := L(a) := 0 S := {Ban ®Çu c¸c nh·n ®-îc khëi t¹o sao cho nh·n cña a b»ng 0, c¸c ®Ønh kh¸c b»ng , S lµ tËp rçng} while z S begin u := ®Ønh kh«ng thuéc S cã nh·n L(u) nhá nhÊt S := S {u} for tÊt c¶ c¸c ®Ønh v kh«ng thuéc S if L(u) + w(u,v) < L(v) then L(v) := w(u,v) {thªm vµo S ®Ønh cã nh·n nhá nhÊt, vµ s÷a ®æi nh·n cña c¸c ®Ønh kh«ng thuéc S} end {L(z) = ®é dµi ®-êng ®i ng¾n nhÊt tõ a tíi z} 1. Input Ma trận có trọng số của đồ thị của mạng 2. Output Mảng lưu đường đi Chỉ rõ khoảng cách ngắn nhất Có giao diện tương tự như hình sau Đồ án hệ điều hành và mạng máy tính 10 NhËn xÐt: Trong thuËt to¸n nµy khi tÝnh to¸n ®-êng ®i tõ nót nguån ®Õn nót n nµo ®ã, ta kh«ng cÇn biÕt gi¸ cña tÊt c¶ c¸c liªn kÕt trong m¹ng mµ chØ cÇn biÕt gi¸ tõ nót ®ã ®Õn c¸c nót l©n cËn cña nã vµ nh·n cña c¸c nót l©n cËn®ã. Nh- vËy thuËt to¸n phï hîp víi ®Þnh ®-êng ph©n t¸n. 3. Tài liệu tham khảo [1]. Nguyễn Thúc Hải, Mạng máy tính và các hệ thống mở, NXB Giáo Dục, 1997. [2]. Behrouz A. Forouzan, DeAnza College, TCP/IP Protocol Suite, second edition, McGraw-Hill, 2000. [3]. Douglas E. Comer, Computer Networks and Internets with Internet Applications, Prentice-Hall,1993. tải về 0.57 Mb. Chia sẻ với bạn bè của bạn:
|