Tài liệu Thuật toán tìm đường đi ngắn nhất trong lý thuyết đồ thị

ĐỀ TÀI: Thuật toán tìm đường đi ngắn nhất trong lý thuyết đồ thị

LỜI NÓI ĐẦU
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đờivà có nhiều ứng dụng hiện đại.Những tư tưởng cơ bản của lý thuyết đồ thị đươc đề xuất từ những năm đầu của thế kỷ 18 bởi nhà Toán học lỗi lạc người Thụy Sĩ Leonhard Euler.Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thàng phố Konigsberg.
Đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau .Chẳng hạn , đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề Giải tích mạch điện.Chúng ta có thể phân biệt các hợp chất hoá học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị.Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin được với nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán như : tìm đường đi ngắn nhất giữa hai thành phố trong cùng một mạng giao thông . Chúng ta còn sử dụng đồ thị để giải các bài toán về lập lịch,thời khoá biểu,và phân bố tần số cho các trạm phát thanh và truyền hình
Mục đích ta tìm hiểu là nhằm 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 tìm đườ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.
Củng cố và rèn luyện kỹ năng lập trình, nhớ lại các thuật toán mà đặc biệt là thuật toán Dijkstra.
Chương 1 : Lý thuyết về thuật toán tìm đường đi ngắn nhất.
Chương 2 : Xây dựng thuật toán.
Chương 3 : Cài đặt thuật toán.
Chương I : LÝ THUYẾT VỀ THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
I.1 Các khái niệm cơ bản của lý thuyết đồ thị
I.1.1 Định nghĩa đồ thị
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này.Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị . Để có thể hình dung được tại sao lại cần đến
các loại đồ thị khác nhau ,chúng ta sẽ nêu ví dụ sử dụng chúng để mô tả một mạng máy tính .Giả sử ta có một mạng gồm các máy tính và các kênh
điện thoại(gọi tắt là tên thoại) nối các máy tính này.Chúng ta có thể biểu
diễn các vị trí đặt máy tính bởi các điểm và các kênh thoại nối chúng bởi
các đoạn nố