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 có trọng lượng nhỏ nhất trong số tất cả những đường đi có thể có. Mặc dù bài toán được phát triển cho đồ thị có hướng có trọng, nhưng các thuật toán sẽ trình bày đều có thể áp dụng cho các đồ thị vô hướng. | CAC BAI TOÁN ĐƯỜNG ĐI 1 Bài toán đường đi ngắn nhất Phát biểu bài toan Cho G X E là một đồ thị co hướng. Ta định nghĩa ánh xa trong lướng như sau L E----- IR e I--- L e xet hai đỉnh i j eX gội P la một đướng đi từ đỉnh i đến đỉnh j trong lướng hay gia cua đướng đi P đước định nghĩa la L P Z eep L e Lý thuyết Đổ thj - Các bài toán đường đi - Khoa CNTT - Đại hoc KHTN 3 Bài toàn đường đi ngàn nhà t Muc đích cua bai toan đướng đi ngan nhai la tìm đướng đi p từ i đen j co trong lương nho nhai trong so tat ca những đướng đi co the co. z-x 8 8 7 k2 3 B D 2 F 5 Lý thuyết Đổ thj - Các bái toán đường đi - Khoa CNTT - Đại hoc KHTN 4 2 Bài toan đường đi ngắn nhất Nhận xét Mặc dù bài toán được phát biểu cho đồ thị co hướng co trong nhưng các thuặt toán sể trình bày đểu cồ thể áp dung cho các đo thị vo hướng co trong báng cách xem moi cánh củá đo thị vo hướng như hái cánh co cung trong lượng nôi cung một cáp đỉnh nhưng co chiểu ngược nháu. Lý thuyết Đổ thj - Các bài toán đường đi - Khoa CNTT - Đại hoc KHTN 5 Bài toàn đường đi ngàn nhà t Nhận xét Khi lám bái toán tìm đướng đi ngán nhất chung tá co thể bo bớt đi các cánh song song vá chỉ chừá lái mọt cánh co trong lướng nho nhất trong so các cánh song song. Đối với các khuyên co trong lướng khong ám thì cung co thể bo đi má khong lám ánh hướng đến kết quá cuá bái toán. Đoi với các khuyển co trong lướng ám thì co thể đưá đến bái toán đướng đi ngán nhất khong co lới giái Lý thuyết Đổ thj - Các bái toán đường đi - Khoa CNTT - Đại hoc KHTN 6
