Bài toán tìm đường đi có nhiều dạng, chẳng hạn như tìm đường đi của
đồ thò có hướng, vô hướng, trọng số của đồ thò có thể là khoảng cách giữa
hai node hay chi phí để đi từ node này đến node kia.

Trong đề tài này em sử dụng phần mềm VISUALL C++, để hiện thực
các giải thuật: Dijsktra, Bellman Ford, Shorttest Path Routing, Floyd. Để từ
đó đánh giá xem việc tìm đường bằng lý thuyết được thực tiển không.

Đề tài này gồm hai phần:

PHẦN I:

Tìm hiểu các giải thuật tìm đường tỉnh .

PHẦN II:

Mô phỏng các giải thuật trên môi trừơng đồ hoạ windows.

Vì thời gian hạn hẹp cũng như kiến thức có gới hạn với lại đây là đề
tài rộng với ba người thực hiện như vì hai người khác chuyển đổi đề tài, nên
em chỉ giải quyết những giải thuật cần thiết trong việc tìm đường đi ngắn
nhất.

Ngày 03 – 7 – 1999.

Sinh viên thực hiện: Lâm Thanh Minh


Chương 1:

MỞ ĐẦU

L: Là quan hệ giữa E và V.
Ví dụ:
Cho đồ thò G(V,E,I) như sau:
V={A,B,C,D}
E={e,f,g,h}
I={(AeB), (AfD), (BhD), (BgC)}
Đồ thò được biểu diễn như sau:
g
e
A

C

h
f
D


2. phân loại đồ thò:
a/ Đồ thò vô hướng và đồ thò hữu hướng:
• Đồ thò vô hướng : Không phân biệt cạnh nối từ đỉnh A đến đỉnh B và từ đỉnh B
đến đỉnh A. Nghóa độ dài chiều AB bằng chiều ngược lại BA.

Ví dụ đồ thò như hình vẽ:

B
g

e
A

e/ Đường đi:
Đường đi giữa hai đỉnh là một chuỗi cạnh nối tiếp nhau nối hai đỉnh đó.
f/ Chu trình:
Là một đường đi khép kín.
3. Cây:
• cây là đồ thò liên thông không có chu trình.
• Mọi cặp đỉnh trong cây có duy nhất một đường nối.
• Đồ thò liên thông có v đỉnh và có v – 1 cạnh là một cây.
• Cây phủ của một đồ thò liên thông là đồ thò con có cùng số đỉnh với đồ thò chứa
nó và là một cây.
4. Biểu diễn của đồ thò:
Cho đồ thò G(V,E). Có hai cách biểu diễn đồ thò trong bộ nhớ tùy theo đồ thò đầy
hay thưa. Đó là biểu diễn bằng ma trận và danh sách.
a/ Danh sách kề:
Danh sách kề là một danh sách liên kết, mỗi phần tử của danh sách kề là một
danh sách chứa các đỉnh mà nó nối tới. Cách biểu diễn này thích hợp với đồ thò
thưa.
b/ Ma trận kề:
Gồm một mảng cấp nxn. Chứa tất cả các đỉnh cũng như chiều dài của các cạnh.
Cách biểu diễn, mỗi phần tử a[i,j]= TRUE (hoặc 1) tức có cạnh nối từ i đến j
ngược lại a[i,j] = FALSE (hoặc 0) nếu không có cạnh nối từ i đến j. Cách biểu
diễn này thích hợp cho đồ thò đầy.
Ví dụ: cho đồ thò.
B
g

e
A

C


1

1

C

0

1

0

0

D
1
1
0
0
5. Chọn cấu trúc dữ liệu cho đồ thò:
Từ việc phân tích trên ta nhận thấy rằng bài toán cho một đồ thò là một mạng máy
tính mà các đỉnh của đồ thò trở thành các máy tính trên mạng, các cạnh trên đồ thò
trở thành đường truyền nối giữa các máy tính trên mạng, các con số được gán trên
đồ thò trở thành lưu lượng đường truyền giữa các máy tính trong mạng. Ngòai ra ta
cũng thấy rằng từ một đỉnh bất kỳ nối tới các đỉnh còn lại là hữu hạn, số đường nối
rất ít. Nhưng vì trong đề tài ta chỉ mô phỏng cho một mạng bằng đồ thò nên tùy
theo giải thuật mà ta có thể qui đònh cho đồ thò là đồ thò hữu hướng hay vô hướng.
Và ta chọn cấu trúc dữ liệu cho đồ thò là ma trận kề và ma trận có trọng số.


8. Distanve vector routing.

C/ các phương pháp tìm đường đi ngắn nhất khác:
9. Fixid routing: Tìm đường cố đònh.
10. Random routing: Tìm đường tình cờ.
11. Adapter routing.
12. Giải thuật leo núi.
13. Giải thuật giá thành nhỏ.
14. Depth First search: Tìm đường theo chiều sâu.
15. Breadth First searc: Tìm đường theo chiều rộng.

Chương 3:
MỘT SỐ VẤN ĐỀ LIÊN QUAN ĐẾN VIỆC TÌM ĐƯỜNG

MÔ HÌNH HỆ THỐNG ROUTING TĨNH
I. GIỚI THIỆU :
Để xem xét một hệ thống mạng phục vụ cho việc tìm đường cho truyền message
như thế nào. Ta xây dựng một mô hình mô phỏng cho mạng để nghiên cứu tính
hiệu quả của mạng phục vụ việc truyền nhận các message như thế nào. Ở đây ta
đánh giá thời gian delay trung bình của mỗi message trong hệ thống.
Mô hình hệ thống routing tónh giống như mô hình hệ thống mạng hàng, gồm mỗi
hàng đơn là M/M/1. Hệ thống này là một mạng hàng mơ,û khách hàng từ ngoài hệ
thống có thể vào bất kỳ Slave nào trên mạng và rời khỏi hệ thống khi được phục
vụ xong. Khách hàng đi trên đường liên lạc của mạng. Đường đi của khách hàng
trong hệ thống được xác đònh trước theo thuật giải tìm đường routing tónh (xác đònh
qij_xác suất mà khách hàng sau khi phục vụ ở Slave i và đi đến nút j).
Mỗi trung tâm xử lý i tương ứng với link i của mạng bao gồm một Slave với tốc độ
phục vụ (i và hàng chờ của các message cần gởi trên mạng(có giới hạn). Hàng
được phục vụ theo cơ chế FIFO. Hàng đợi ở mỗi node là có giới hạn vì thường tài
nguyên của mạng đều có giới hạn. Tốc độ đến của khách hàng (message) vào hệ

Hàng đợi được quản lý theo cơ chế FIFO.
Message (khách hàng) vào hệ thống tại nút bất kì và ra khỏi hệ thống khi message
đó đã đến đích cần gởi đến.
Điều kiện để kết thúc mô phỏng là thời gian mô phỏng đạt đến thời gian đònh
trước.
Vấn đề tìm đường trong hệ thống mạch chuyển gói phức tạp hơn trong hệ
thống chuyển mạch điện tử.
- Chức năng của mạch chuyển gói là nhận những gói từ trạm nguồn và cung cấp
nó đến người nhận. Để hoàn thành việc đó một con đường hay một routing
thông qua mạng được chọn, thông thường khả năng cho phep nhiều hơn. Điều
đó có nghóa là con đường được chọn phải mạnh. Đảm bảo một só yêu cầu cần
thiết trong chức năng đường truyền như thoả mản các tính chất sau:
• Correctrer and Simplicity ( đúng và đơn giản). Đảm bảo các packet phải đến
được nơi nhận và thuật toán phải dể hiện thực.
• Robustrer (Linh động). Có khả năng hoạt động ngay sau khi thay đổi về hệ
thống.
Thay đổi:
Topology.
Traffic.
Cũng như những sự cố bất thường xãy ra trong một mạng máy tính thường xuyên.
• Công bằng và tối ưu: Các thuật toán phải đảm bảo công bằng và cố gắng truyền
các packet tới nơi nhận nhanh nhất.


- Sự chọn đường thường dựa vào tiêu chuẩn đơn giản là chọn đường đi ngắn nhất
(một đường thông qua mạng với it1 node nhất ) thông qua mạng. Tiêu chuẩn chung
cho đường ngắn nhất là đường giá trò nhỏ nhất không trong trường hợp đó, giá trò
bao gồm cho tường đường, và đường thông qua mạng bao gồm tích lũy giá trò bé
nhất.
- Để giải quyết các yêu cầu trên người ta đưa ra các giải thuật tìm đường đi ngắn

- Tìm đường tập trung: Được tập trung bởi sự tồn tại của một hoặc vài trung tâm
điều khiển mạng thực hiện việc chọn đường sau đó gửi các bản tìm đường tới
tất cả các nút dọc theo con đường đã được chọn. Trong trường hợp này thông
tin tổng thể của mạng cần dùng cho việc tìm đường chỉ được cất giữ tại trung
tâm điều khiển mạng.
Các nút mạng có thể không gửi bất kỳ thông tin nào về trạng thái của chúng tới
trung tâm hoặc gửi theo đònh kỳ, hoặc gửi theo một sự kiện nào đó.


Tìm đường phân tán: Không tồn tại các trung tâm điều khiển, quyết đònh tìm
đường được thực hiện tại mỗi nút của mạng. Điều này đòi hỏi việc trao đổi
thông tin giữa các nút, tuỳ theo mức độ thích nghi của giải thuât5 được sử
dụng.
- Tìm đường tónh: Có thể là tập trung hay phân tán nhưng nó không đáp ứng với
mọi sự thay đởi trên mạng. Trong trường hợp này, chọn đường được thực hiện
mà không có sự trao đổi thông tin, khôn g đo lường và không cập nhật thông
tin. Tiêu chuẩn tối ưu để chọn đường và bản thân con đường được chọn một lần
cho toàn cuộc, không hề có sự thay đổi giữa chúng. Các kỹ thuật tìm đường
tónh rõ ràng là rất đơn giản, do vậy sử dụng rất rộng rãi, đaặc biệt trong các
mạng tương đối ổi đònh it1 có thay đổi về topology và lưu thông trên mạng .
- Tìm đường động: Thu hút sự quan tâm của các nhà thuyết kế mãng do khả
năng thuyết kế đáp ứng đối với các trạng thái khác nhau của mạng, vì đây là
yếu tố quan trọng, đặc biệt đối với các ứng dụng, thời gian thực trong đó yêu
cầu đầu tiên của người sử dụng là mạng phải có khả năng cung cấp được các
con đường khác nhau để dự phòng sự cố và thích nghi nhanh chóng với các
thay đổi trên mạng. Mức độ thích hợp của một kỹ thuật con đường được đặc
trưng bởi trao đổi thông tin chọn đường trên mạng
⊗ Tóm lại: Trong đề tài này em tìm hiểu các giải thuật tìm đường trong lý thuyết
và thực tế đã áp dụng các kỹ thuật tìm đường đã nêu ở trên. Và khi tìm hiểu các
giải thuật tìm đường ứng dụng trong lý thuyết và thực tế để hiểu rỏ hơn về cách

Thực hiện routing tất cả các đỉnh cùng một lúc. Nó loại bỏ được tính phụ thuộc thứ
tự cuả giải pháp tuần tự nhưng lại có độ phức tạp tính toán quá lớn. Hiện nay chưa
có một giải thuật có độ phức tạp cấp đa thức nào đưa ra, ngay cả giải thuật cho các
net có hai điểm. Hiện nay người ta đang xem xét giải pháp đồng thời dựa trên
phương pháp integer programming.
• Giải pháp động:
Các đối tượng tại các đỉnh có thể chuyển động, mà ta thực hiện việc tìm đủi giữa
các đối tượng. Ví dụ như có hai đối tượng A và B tại một thời điểm nào đó hai đối
tượng này ở tại hai đỉnh khác nhau, nhưng chúng chuyển động với hai vận tốc khác
nhau. Đến một lúc nào đó hai đối tượng này gặp nhau, thì đây chính là điểm dừng
của giải pháp động.

A. Lập trình song song
1. Mục đích:
Mục đích của xử lý song song là thực hiện việc tính toán nhanh hơn hay giải quyết
vấn đề lớn như : điều khiển không lưu, dự báo thời tiết, hệ thống thời gian thực…
Để giải quyết những vấn đề này người ta phải chia nhỏ vấn đề ra và sử dụng
nhiều processor để tính toán song song. Có hai hệ thống được ứng dụng để giải
quyết vấn đề này.
a) Máy tính song song:
Máy này bao gồm một nhóm các processor cùng loại, được kết nối với nhau theo
một mô hình nào đó để cho phép chúng cùng hoạt động và trao đổi dữ liệu cho
nhau.
b) Hệ thống phân bố:
Là hệ thống gồm nhiều processor có thể có kiễu khác nhau và được phân bố trên
một vùng đòa lý rộng (mạng máy tính).
2. Đánh giá hiệu quả của giải thuật song song:
Cách tính 1 :
Lấy B là vấn đề cần tính toán, n là kích thước của bài toán. Độ phức tạp của giải
thuật tuần tự để giải quyết vấn đề là T*(n). với giả sử là không có giải thuật tuần

Xãy ra khi một hoạt động sử dụng vò trí nhớ được nạp bởi một hoạt động sau đó.
Ví dụ: cho các phát biểu
A=B+C (1)
C=B*5 (2)
A=D-6 (3)
Phát biểu (1) phải được thực hiện trước phát biểu (2) vì (1) sử dụng giá trò hiện tại
của C.
•Output dependence
Xãy ra khi một hoạt động nạp một vò trí nhớ mà vò trí nhớ này cũng được nạp ở
hoạt động sau. trong ví dụ trên, phát biểu (3) phải thực hiện sau phát biểu (1) nếu
không A sẽ chứa dữ liệu sai.
- Sự phụ thuộc điều khiển (control dependence)
loại phụ thuộc này là do dòng điều khiển trong chương trình. Trong ví dụ sau, phát
biểu 2 được thực thi phụ thuộc vào kết quả kiểm tra điều kiện 1.
If (x
Giải thuật giá trò bé nhất:
Thực tế các mạch chuyển mạch gói(PSN) sự quyết đònh đường của nó dựa trên
một số dạng phân loại giá trò tối thiểu. Nếu sự phân loại theo giá trò các hops là ít
nhất, mỗi đường có giá trò 1. Điển hình hơn, giá trò mỗi đường tương xứng dung
lượng mỗi đường, tương xứng tức thời (current load) trên đường đi, hoặc một số tổ
hợp. Trong một số trường hợp, sự đánh giá các giá trò đó không bao gồm giải thuật
giá trò bé nhất.Với điều đó có thể nói đơn giản:


Cho một mạng các Node nối với nhau bằng những đường hai chiều, mỗi
đường đó có giá trò tổng hợp chung cho mỗi hướng. Ta đònh nghóa giá trò của một
đường (path) giữa hai Node là tổng giá trò của những đường nó đi qua. Cho mỗi
cặp Node tìm thấy một con đường giá trò bé nhất. Hầu hết các giải thuật giá trò bé
nhất được sử dụng trong PSN đều dựa trên hai giải thuật Dijkstra và Bellman Ford.

1. Giải thuật Dijkstra:

Giải thuật Dijkstra có thể phát biểu như sau: Để tìm con đường ngắn nhất từ Node
nguồn cho trước đến tất cả các Node khác bằng cách phát triển thêm vào độ dài
của đường. Quá trình thực hiện giải thuật như sau: Với mức k con đường ngắn nhất
đến k Node, đến Node nguồn đã cho, qua m Node, ở mức(k+1).
Giải thuật được đònh nghóa như sau:
N = số lượng Node trong mạng.
S = Node nguồn.
M = số lượng Node hợp nhất cho giải thuật (kết hợp cho giải thuật).
Dij = Giá trò đường từ Node i tới Node j.
→dij = 0
dij = ∞ nếu Node không nối trực tiếp.
Dn = Giá trò nhỏ nhất từ Node s đến Node n lúc xác lập giải thuật.
Giải thuật có 3 bước và lập lại cho đến khi M = N.

cho trước với tất các đỉng khác trong đồ thò.
Giả sử giải thuật Dijsktra được áp dụng cho một đồ thò có n đỉnh và E cạnh. Thời
gian của bước khởi tạo mảng D và P tỉ lệ với n. Số lần so sánh để chọn đỉnh v
trong tập hợp C là n-1, n-2,…2 (số bước lập là n – 2). Như vậy, thời gian thực hiện
giải thuật là tỉ lệ với n2.
Nếu E

3

5

1

5

2

1

3

1

2

4

2
1[0]

5

1

2



• giải thuật Dijkstra thực hiện từng bước như sau:
Ví dụ: Xét đồ thò:
2

B
2

4

2
D

A

C

E

4

3

1

1

7

H

A B C D E F G H
D
D
0 2 ∞ 4 ∞ 1 6 ∞


V

A A F A A F A
2

4

0

1

6

Cứ tiếp tục như trên ta lần lược có các bảng như sau:
A B C D E F G H
D
D D
D
L
0 2 4 4 4 1 6 ∞
V
A B F B A F A

0


6

1

6

5


D
L
V

A B C D E F G H
D D D
D
0 2 4 4 4 1 6 5
A B F B A F C

0

D
L
V

2

4


5


D
L
V

A B C D E F G H
D D D D
D
0 2 4 4 4 1 6 5
A B F B A F C

0

D
L
V

2

4

4

6

1

6



L
V

0 2 4 4 4 1 6 5
A B F B A F C

0

2

4

4

6

1

6

5

Giải thuật kết thúc và bảng lập được sau cùng cho ta con đường ngắn nhất nối từ
đỉnh A đến các đỉnh khác.
Ví dụ đường đi ngắn nhất nối từ đỉnh A đến H là ABCH và chiều dài đường ngắn
nhất này là 5.

2. Giải thuật BELLMAN FORD:


h = h + 1.

Giá trò đường dẫn từ Node nguồn cho tới các Node khàc = Giá trò đường
dẫn ngắn nhất từ Node nguồn khi chưa tăng h + chi phí từ Node xét đến
các Node lân cận nó.

Kiểm tra giá trò đường dẫn có
giá trò thay đổi so với lúc chưa
tăng h.
T

F

Giữ nguyên
bảng tìm
đường đang
xét


•

Bảng cho ta kết quả của giải thuật như sau:
( tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6)

2
2

3


1-2
3
1-4-5-3

5
1

3

6
2

1

D4(h) Path
∞ 1 1-4
1 1-4
1 1-4
1 1-4

5

D5(h) Path
∞ ∞ 2 1-4-5
2
1-4-5
2
1-4-5

D6(h) Path

- Nếu Node đó có chi phí chưa xác đònh thì cho giá trò bằng giá trò vừa tìm được
và cho tên là tên của Node làm việc.
- Nếu Node đó có chi phí lớn hơn chi phí vừa tính được thì thay giá trò vừa tìm
được và tên là tên của Node vừa tìm được.
- NếU Node đó có chi phí nhỏ hơn chi phí vừa tính được thì lấy giá trò của Node
đó và tên chính là tên của Node đó.
c) Xem sét tất cả các Node thử có chi phí xác đònh, Node nào có chi phí nhỏ nhất
thì được chuyển thành Node cố đònh và là Node làm việc cho Node kế tiếp.
d) Trở lại bước hai cho đến khi tìm được một đường đi có chi phí nhỏ nhất từ
Node nguồn cho tới Node đích.
Nhập vào đỉnh nguồn và là đỉnh làm
việc
Gán chiều dài đỉnh nguồn = 0
Gán chiều dài các đỉnh khác = ∞
-

Xét các đỉnh kề đỉnh hiện hành
Tính chiều dài của các đỉnh kề

Đỉnh có chiều dài nhỏ hơn chiều
dài vừa tính được

F

Thay giá trò vừa tìm được
Tên là tên của đỉnh vừa
tìm

T
Giữ nguyên giá trò đó

3

2

A

G(,
G 2
_)
A(0, _)6
1

7

B

2
A G(4, B)
6

1

2

G

3

2 _)



A G(4, B)G 2
6

1
E
4
E(5, G)

F

E A)
E(6,

3

H H(, _)

2

1

B(2, A) B
2
2

C(, _)

C


C C(9, B)

3

3

H H(6, G) D

2

2
F
F(9, E)

D(,_
))
___)

F(9,
E)
B(2,
B
C C(9,
B(2, A) B
A)
B)
C C(9, B)
7
2
3

4
E
G(5, A)
F(8, H)
B(2, A) B
C(9,
B)
C
2

2
2
A G(4, B)
G
6

1
E
G(5, A)

3

3

H H(6, G) D

2
4

2