Khoa : Công nghệ thông tin .

Đề Tài : “ Các thuật toán tìm đường đi ngắn nhất trong đồ thị ”

* MỤC LỤC

Chương : MỞ ĐẦU

1. Mục đích : Giới thiệu các khái niệm cơ bản , các bài toán ứng dụng quan trọng của lý thuyết đồ thị như bài toán cây khung nhỏ nhất , bài toán đường đi ngắn nhất Và những thuật toán để giải quyết chúng đã được trình bày chi tiết cùng với việc phân tích và hướng dẫn cài đặt chương trình trên máy tính .

2. Củng cố , rèn luyện kỹ năng lập trình và nhớ lại các thuật toán .

Chương I : LÝ THUYẾT VỀ THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT

1. Các khái niệm cơ bản của lý thuyết đồ thị .

a. Định nghĩa đồ thị .

b. Các thuật ngữ cơ bản .

c. Định nghĩa đường đi,chu trình, đồ thị liên thông .

2. Các khái niệm mở đầu về đề tài cần đề cập tới .

3. Đường đi ngắn nhất xuất phát từ một đỉnh .

4. Thuật toán Dijkstra . ( Nêu cụ thể một bài toán ).

5. Đường đi trong đồ thị không có chu trình .

6. Đường đi ngắn nhất giữa tất cả các cặp đỉnh .

Chương II : XÂY DỰNG THUẬT TOÁN

1. Thuật toán đường đi trong đồ thị không có chu trình .

2. Thuật toán đường đi ngắn nhất giữa các cặp đỉnh .

3. Thuật toán Dijkstra . Áp dụng cho bài toán nêu trên .

Chương III : CÀI ĐẶT THUẬT TOÁN

Chọn : Tìm đường đi ngắn nhất từ một đỉnh này đến đỉnh kia theo thuật toán Dijkstra .

* KẾT LUẬN & HƯỚNG PHÁT TRIỂN.

* TÀI LIỆU THAM KHẢO