Thuật toán floyd - Tìm đường đi ngắn nhất

Chào các bạn,bài trước mình đã làm bài tập về tìm đường đi ngắn nhất dùng thuật toán Dijkstra.Và hôm nay,cũng bài toán tìm đường đi ngắn nhất nhưng chúng ta tìm hiểu với thuật toán mới hơn nhé!Đó là thuật toán gì nào?Các bạn đoán xem.Hii các bạn đoán đúng rồi đó là thuật toán Floyd-Warshall.Giờ ta cùng tìm hiểu nó nhé!

Thuật toán Floyd-Warshall còn được gọi là thuật toán Floyd được Robert Floyd tìm ra năm 1962.thuật toán Floyd là một thuật toán giải quyết bài toán đường đi ngắn nhất trong một đồ thị có hướng có cạnh mang trọng số dương dựa trên khái niệm các Đỉnh Trung Gian.
Thuật toán Floyd-Warshall giúp xác định tất cả các Đường đi ngắn nhất giữa tất cả các cặp đỉnh.
Định lý: Thuật toán Floyd-Warshall cho ta Ma trận W* = Wn là ma trận Khoảng cách nhỏ nhất của đồ thị G.

Đến đây ta cùng làm một phép so sánh nhé:

So sánh giữa 2 thuật toán dijkstra và Floyd-Warshall

Dijkstra Floyd-Warshall
Ưu điểm Chi phí thấp hơn Thuật toán Floyd-WarshallChi phí thấp hơn Thuật toán Floyd-Warshall Không cần chạy lại Thuật toán (có nghĩa là có tính kế thừa từ đường đi lẫn nhau)
Có thể chạy được với trong số âm.
Nhược điểm Không chạy được với trọng số âm. Chi phí cao O(n^3) cho mỗi cặp đỉnh

Mã giả:

Thuật toán floyd thuần:

Thuật toán floyd mở rộng:

Trên đó là phần lý thuyết mình đã search tham khảo trên wiki và slide của thầy Trần Quốc Việt,giờ mình đi thẳng vào code luôn nhé!

Ma trận test trong code là:

Dựa vào phần mã giả và ma trận ví dụ cho trên mình đã viết code như sau,mình có chú thích cho các bạn rồi,các bạn xem xem có hiểu không nhé,nếu có thắc đừng quên comment bạn nhé,nếu mình chậm trả lời thì liên hệ facebook mình hổ trợ trực tiếp luôn nè.

Đây là video mình giải thích thêm về lý thuyết và code nè,các bạn xem thêm nếu có nhu cầu nhé!

Chúc các bạn hoàn thành tốt bài tập này nhé!

Lưu ý là thuật toán trên mình tự code nên chắc chắn không thể không có sai sót nên mong các bạn thông cảm và chỉ dùng để tham khảo thôi nhé.

Giấy phép Creative Commons Giấy phép Creative Commons Attribution-ShareAlike 4.0 Quốc tế .

Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :