tailieunhanh - Chương IV: Các bài toán đường đi

Mục đích của bài toán đường đi ngắn nhất là tìm đường đi P từ i đến j mà có trọng lượng nhỏ nhất trong số tất cả những đường đi có thể có. | Khoa Công nghệ Thông tin ĐHKHTN. CHƯƠNG IV. CAC BAI TOAN ĐƯỜNG ĐI Bài toán đường đi ngắn nhát Phắt biểu bài toàn Cho G X E là một đổ thị co hướng. Ta định nghĩa anh xa trong lướng như sau L E IR e I---- L e Xét hai đỉnh i j eX gội P la một đướng đi tư đỉnh i đen đỉnh j trong lướng hay gia cua đướng đi P đước định nghĩa la L P E eeP L e Muc đích cua bai toan đướng đi ngan nhat la tìm đướng đi P tư i đen j ma co trong lướng nho nhat trong so tat ca nhưng đướng đi co thê co. Nhan xet. - Mặc du bai toan đước phat bie u cho đo thị co hướng co trong nhưng cac thuật toan se trình bay đeu co the ap dung cho cac đo thị vo hướng co trong bang cach xem moi canh cua đo thị vo hướng như hai canh co cung trong lướng nối cung mọt cạp đỉnh nhưng co chieu ngước nhau. - Khi lam bai toán tìm đướng đi ngan nhat thì chung ta co the bo bớt đi cac canh song song va chỉ chưa lai mot canh co trong lướng nho nhat trong so cac canh song song. Đề cương bài giảng môn Ly thuyết đồ thị trang IV 1 Khoa Công nghệ Thông tin ĐHKHTN. - Đối với các khuyên co trọng lượng không âm thì cũng co thê bô đi má không lâm ánh hướng đên kêt quá cũá bái tôán. Đối với các khuyên cô trọng lượng ám thì cô thê đưá đên bái tôán đướng đi ngán nhát không cô lới giái xem . - Dô các nhán xêt vưá nêu cô thê xem dư liêu nháp cũá bái tôán đướng đi ngán nhát lá má trán L đước định nghĩá như sáu trông lướng cánh nhô nhát nôi i đến j nếu cô Lii a 0 nêu không cô cánh nôi i đên j. Trông quá trình báy các thuát tôán đê chô tông quát giá trị 0 trông má trán L cô thê tháy thể báng w. Tuy nhiên khi cái đát chướng trình chung tá ván cô thê dung 0 tháy vì w báng cách đưá thêm môt sô lênh kiê m trá thích hớp trông chướng trình. Nguyên ly Bellman Hau hết các thuật toán tìm đường đi ngắn nhất đều đặt cơ sờ trền nguyền ly Bềllman đáy lá nguyền ly tong quát cho các bái toán toi ưu hOá rơi rac đoi vơi trương hơp bái toán đương đi ngán nhát thì co thề trình báy nguyền ly náy như sáu. L P1 L P1 L Pi P2 L Pi P2 L P Đề