Tham khảo tài liệu 'graph - phần 4', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 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 noi cung mot cạp đỉnh nhưng co chieu ngước nhau. - Khi lam bai toan 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 Háu hêt các thuát tôán tìm đướng đi ngán nhát đêu đát cớ sớ trên nguyên ly Bêllmán đáy lá nguyên ly tông quát chô các bái tôán tôi ưu hôá rới rác đôi với trướng hớp bái tôán đướng đi ngán nhát thì cô thê trình báy nguyên ly náy như sáu. L P1 L P1 L Pi P2 L Pi P2
