Toán RR(BT+bài giải) exercise9 circuit answer

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

Bài tập chương 9

Đường đi và chu trình

1 Dẫn nhập

Trong bài tập dưới đây, chúng ta sẽ làm quen với các lý thuyết liên quan tới đường đi và

chu trình. Sinh viên cần ôn lại các lý thuyết liên quan được trình trong chương 9, trước

khi làm bài tập bên dưới.

2 Bài tập mẫu

Đồ thị G1 như hình bên dưới đây.

S

A

B

C

D

E

F

G

H

(G1)

10

10

14

11

6

8

5

2

7

3

2 4

4

8

6

Câu 1.

Tìm đường đi ngắn nhất xuất phát từ S đến tất cả các đỉnh còn lại bằng thuật giải

Dijkstra.

Lời giải. Dijkstra:

Giáo trình Toán Rời Rạc 1 Trang 1/17