BÀI TẬP TOÁN RỜI RẠC
---&0&--
CHƯƠNG 4:
MỘT SỐ BÀI
MỘT SỐ BÀI
TOÁN TỐI ƯU
TOÁN TỐI ƯU
TRÊN ĐỒ THỊ
TRÊN ĐỒ THỊ
Giảng viên : Nguyễn Mậu Hân
Sinh viên thực hiện : Nguyễn Thị Diệu Hằng
Lớp : Tin K30D
* Bài 1:
Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến các
đỉnh khác trong đồ thị sau:
Lời giải:
L(a) L(b) L(c) L(d) L(e) L(g) L(h) L(k)
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ a
- 4 ∞ ∞ ∞ 11 2 ∞ b
- 4 ∞ 7 ∞ 9 - 3 c
- 4 5 7 15 9 - - d
- - 5 7 15 9 - - e
- - - 7 15 8 - - g
- - - - 14 8 - - h
- - - - 13 - - - k
b
a
k
h
c
e

- - - - - - - - 10 9 i
10 - k
a
c
b
g
d
i
f
h
e
k
1
10
6
3
2
4
10
4
1
4
1
3
6
8
5
3
2
5

- - - - 19 - - - 18 - - - - 23
L
- - - - 19 - - - - - - - - 20
M
- - - - - - - - - - - - - 20
N
* Bài 4:
A
F
J
G H I
K
B
L
C
M
D
N
E
7 3 8 3
2 9 5 7
1 4 2 2 3
4 3 2 2 5 2 2 5
2
3
4
5 3 4 3 2
Tìm đường đi ngắn nhất từ B đến các đỉnh khác của đồ thị có ma trận
trọng số là:
A B C D E F G

4
1
4
2
2
1
4
4
A B C D E F G
A 3 6
B 3 2 4
C 6 2 1 4 2
D 4 1 2 4
E 4 2 2 1
F 2 2 4
G 4 1 4
W=W
0
Áp dụng thuật toán Floyd ta có:
A B C D E F G
A 3 6
B 3 6 2 4
C 6 2 12 1 4 2
D 4 1 2 4
E 4 2 2 1
F 2 2 4
G 4 1 4
W
1
A B C D E F G

A 6 3 5 6 8 7 9
B 3 4 2 3 5 4 6
C 5 2 2 1 3 2 4
D 6 3 1 2 2 3 3
E 8 5 3 2 4 2 1
F 7 4 2 3 2 4 3
G 9 6 4 3 1 3 2
W
5
=W
6
A B C D E F G
A 6 3 5 6 8 7 9
B 3 4 2 3 5 4 6
C 5 2 2 1 3 2 4
D 6 3 1 2 2 3 3
E 8 5 3 2 2 2 1
F 7 4 2 3 2 4 3
G 9 6 4 3 1 3 2
W
7
=W
*
* Bài 5:
Tìm W
*
bằng cách áp dụng thuật toán Floyd vào đồ thị sau:
Lời giải:
Ta có ma trận trọng số của đồ thị trên là: (những ô trống là ∞)
A B C D E F

6
13
43
5
8
2