TAILIEUCHUNG - GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CHƯƠNG 6

BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Trong các ứng dụng thực tế, vài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị liên thông có một ý nghĩa to lớn. Có thể dẫn về bài toán như vậy nhiều bài toán thực tế quan trọng. Ví dụ, bài toán chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn hoặc khoảng cách hoặc thời gian hoặc chi phí) trên một mạng giao thông đường bộ, đường thủy hoặc đường không; bài toán chọn một phương pháp tiết kiệm nhất để đưa ra một hệ thống động. | CHƯƠNG 6 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Trong các ứng dụng thực tế vài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị liên thông có một ý nghĩa to lớn. Có thể dẫn về bài toán như vậy nhiều bài toán thực tế quan trọng. Ví dụ bài toán chọn một hành trình tiết kiệm nhất theo tiêu chuẩn hoặc khoảng cách hoặc thời gian hoặc chi phí trên một mạng giao thông đường bộ đường thủy hoặc đường không bài toán chọn một phương pháp tiết kiệm nhất để đưa ra một hệ thống động lực từ trạng thái xuất phát đến trạng một trạng thái đích bài toán lập lịch thi công các công các công đoạn trong một công trình thi công lớn bài toán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng thông tin . Hiện nay có rất nhiều phương pháp để giải các bài toán như vậy. Thế nhưng thông thường các thuật toán được xây dựng dựa trên cơ sở lý thuyết đồ thị tỏ ra là các thuật toán có hiệu quả cao nhất. Trong chương này chúng ta sẽ xét một số thuật toán như vậy. 1. CÁC KHÁI NIỆM MỞ ĐẦU Trong chương này chúng ta chỉ xét đồ thị có hướng G V E V n E m với các cung được gán trọng số nghĩa là mỗi cung u v I E của nó được đặt tương ứng với một số thực a u v gọi là trọng số của nó. Chúng ta sẽ đặt a u v nếu u v I E. Nếu dãy Vo V1 . . . Vp là một đường đi trên G thì độ dài của nó được định nghĩa là tổng sau p ảa vi-i Vi . i 1 tức là độ dài của đường đi chính là tổng của các trọng số trên các cung của nó. Chú ý rằng nếu chúng ta gán trọng số cho tất cả cung đều bằng 1 thì ta thu được định nghĩa độ dài của đường đi như là số cung của đường đi giống như trong các chương trước đã xét . Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể phát biểu như sau tìm đường đi có độ dài nhỏ nhất từ một đỉnh xuất phát s I V đến đỉnh cuối đích t I V. Đường đi như vậy ta sẽ gọi là đường đi ngắn nhất từ s đến t còn độ dài của nó ta sẽ ký hiệu là d s t và còn gọi là khoảng cách từ s đến t khoảng cách định nghĩa như vậy có thể là số âm . Nếu như không tồn tại đường đi từ s đến t thì ta sẽ đặt d s t .

• Kĩ thuật Viễn thông
• biểu diễn đồ thị
• thuật toán
• đồ thị euler
• phương pháp biểu diễn
• cây khung
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• biểu diễn hình học
• biêu diễn đồ thị bằng ma trận
• biểu diễn đồ thị bằng bảng
• sự đẳng cấu của các đồ thị
• Số cạnh của đồ thị
• Cách biểu diễn đồ thị
• Ma trận trọng số
• Bài toán trên đồ thị
• Gom cụm đồ thị
• Khối thông điệp
• Diễn đàn thảo luận
• Bài toán gom cụm phẳng
• Biểu diễn văn bản bằng đồ thị
• Gom cụm đồ thị bằng mạng Kohonen
• tài liệu về đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Bài giảng Toán rời rạc
• Đồ thị liên thông
• Biểu diễn đồ thị bằng ma trận
• Bài toán đường đi ngắn nhất
• Tiếp cận kết thúc mở
• Biểu diễn trực quan
• Biểu diễn đồ thị hàm số
• Hàm bậc hai
• Tính chất của dãy số
• Dạy học toán
• Khái niệm đồ thị
• đồ thị con
• đồ thị riêng
• sự đẳng hình của đồ thị
• định nghĩa đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• Đồ thị phẳng
• bài toán luồng trên mạng
• tài liệu lý thuyết đồ thị
• đồ thị có hướng
• đồ thị hữu hạn
• đồ thị vô hạn
• Tìm kiếm trên đồ thị
• Đồ thị Hamilton
• Thuật toán đồ thị
• Ứng dụng tìm kiếm trên đồ thị
• Bài toán cây khung nhỏ nhất
• Thuật toán duyệt đồ thị