1. ĐỒ THỊ
2
KHOA CÔNG NGHỆ THÔNG TIN
1. ĐỒ THỊ
3
KHOA CÔNG NGHỆ THÔNG TIN
1. ĐỒ THỊ
4
KHOA CÔNG NGHỆ THÔNG TIN
2. CÂY
5
KHOA CÔNG NGHỆ THÔNG TIN
2. CÂY
6
KHOA CÔNG NGHỆ THÔNG TIN
3. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
Ví dụ 5: Biểu diễn đồ thị vô hướng trong hình sau bằng ma trận kề
7
KHOA CÔNG NGHỆ THÔNG TIN
3. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
8
KHOA CÔNG NGHỆ THÔNG TIN
4. THUẬT TOÁN ĐƯỜNG ĐI NGẮN NHẤT – DIJKSTRA’S 4.1 Phát biểu bài toán
9
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
10
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
11
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
12
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
13
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
14
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
15
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
16
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
17
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
18
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
19
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
(Hình 2)
20
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
(Hình 3)
21
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
(Hình 4)
22
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
(Hình 5)
23
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
(Hình 6)
24
KHOA CÔNG NGHỆ THÔNG TIN
4.2 Thuật toán đường đi ngắn nhất
25
KHOA CÔNG NGHỆ THÔNG TIN
#BÀI TẬP 1:
26
KHOA CÔNG NGHỆ THÔNG TIN
#BÀI TẬP 2:
a)Viết ma trận kề từ đồ thị vô hướng hình 1 b)Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong đồ thị vô hướng hình 1
27
KHOA CÔNG NGHỆ THÔNG TIN
#Thực hành 01:
#Nhận xét: input, output ??
28
KHOA CÔNG NGHỆ THÔNG TIN
#Thực hành 02:
#đồ thị có hướng
>>> g = Graph(6) >>> g.graph = [[0, 3, 0, 4, 0, 0],
[0, 0, 6, 2, 0, 0], [0, 0, 0, 0, 4, 3], [0, 0, 1, 0, 4, 0], [0, 0, 0, 0, 0, 5], [0, 0, 0, 0, 0, 0]
]; >>> g.timduongdi(0);
#Nhận xét: input, output của thuật toán đường đi ngắn nhất
#Yêu cầu – comment vào dấu note, bước lặp, vòng lặp của giải thuật
29
KHOA CÔNG NGHỆ THÔNG TIN
#Thực hành 03:
a)Viết ma trận kề từ đồ thị có hướng (hình 1) b)Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z (đỉnh 0 đến đỉnh 5) trong đồ thị có hướng (hình 1)
30
