MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ -
PHẦN 4

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: 2. 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:
c

b

e

d

k

h

a

g


4

3. Cho đồ thị có trọng số như hình dưới đây. Hãy tìm đường đi ngắn nhất từ đỉnh
A đến đỉnh N.
e

i

k

a

10

6
3
1
4


G

L

H

M

I

7
3 8
3
2 9
5
7
3
5
2
2
3
2
2
4
6
3
2
2
2





414
422
1224
4214
24126
423
63

5. Tìm W* bằng cách áp dụng thuật toán Floyd vào đồ thị sau:
N

A
B
C D
E
F
G
A
B
C

1
6. Giải bài toán mạng vận tải sau bằng thuật toán Ford-Fulkerson với luồng vận tải
khởi đầu bằng 0.

7. Giải bài toán mạng vận tải sau bằng thuật toán Ford-Fulkerson với luồng vận tải
khởi đầu được cho kèm theo. v
5

v
2

v
6

v
3

v

2

8

v
1

v
0

v
7

10
6

8

8

10
20
10
15
8
6
2
8
0
16











874325
346294414
2120271423
07331122
23342169
2432144525
.
v
3

v
2

v
4

v
5

v

1

8

15
6

10
3

30
6
0
2
2
0
2
0
0
10

16

3 25

7
2
0
0
0