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

Với sự ra đời của Internet, tất cả các trường học hiện nay đều đã áp dụng các kiến thức, kĩ năng và hiểu biết về công nghệ thông tin trong các môn học nhằm nâng cao hiệu quả dạy và học. Trong khoa học máy tính và trong toán học, thuật toán tìm đường đi ngắn nhất trong đồ thị là một bài toán thường được vận dụng trong các ứng dụng tin học. Trong các ứng dụng thực tế, bài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị có một ý nghĩa to lớn. Ví dụ, bài toán chọn một hành trình tiết kiệm nhất (về tiêu chuẩn khoảng cách, thời gian hoặc chi phí) trên một mạng lưới giao thông đường bộ, đường thủy,..ện nay có rất nhiều các 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ị là hiệu quả cao nhất. Sau đây chúng ta sẽ xét đến thuật toán Floyd Warshall, một trong những thuật toán tìm đường đi ngắn nhất được xây dựng dựa trên lí thuyết đồ thị. Mong thầy và các bạn theo dõi và góp ý để chủ đề của chúng em được hoàn thiện hơn.

I. GIỚI THIỆU CHUNG:

1. Lịch sử lý thuyết đồ thị:

Bài toán bảy cây cầu Euler, còn gọi là Bảy cầu ở Konigsberg là bài toán nảy sinh từ thành phố Konigsberg, Phổ. Bài toán đặt ra là tìm một tuyến đường mà đi qua mỗi cây cầu một lần và chỉ đúng một lần (bất kể điểm xuất phát hay điểm tới). Năm 1736, Leonhard Euler đã chứng minh rằng bài toán này là không có lời giải. Kết quả này là cơ sở phát triển của lý thuyết đồ thị.

Năm 1852 Francis Guthrie đưa ra bài toán bốn màu về vấn đề liệu chỉ với bốn màu có thể tô màu một bản đồ bất kì sao cho không có hai nước nào cùng biên giới được tô cùng màu. Bài toán này được xem như đã khai sinh ra lý thuyết đồ thị và chỉ được giải sau một thế kỉ vào năm 1976 bởi Kenneth Appel (1932 -) và Wolfgang Haken (1928 - ). 2. Sơ lược về thuật toán Floyd Warshal: 2. Giới thiệu: 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 tìm đường đi ngắn nhất trong một đồ thị có hướng dựa trên các đỉnh trung gian. Khi cần chỉ ra đường đi ngắn nhất của mọi cặp đỉnh trong đồ thị thì thuật toán Floyd chính là công cụ giúp ta thực hiện chỉ trong một lần chạy. Hơn thế nữa, cách tiếp cận và cài đặt của nó cũng khá đơn giản và quen thuộc. 2. Tác dụng: Thuật toán Floyd-Warshall được thiết kế để tính toán đường đi ngắn nhất giữa mọi cặp điểm trong đồ thị có hướng. 2. Ưu điểm:

• Tìm được đường đi ngắn nhất giữa tất cả các điểm trong đồ thị với trọng số âm hoặc dương, trong đồ thị có hướng hoặc vô hướng.
• Chỉ với một lần chạy thuật toán sẽ cho ta kết quả.
• Phát hiện được chu trình âm trong đồ thị.
• Đồ thị có hướng: là một cặp không có thứ tự G=(V, A), trong đó: ● V là tập các đỉnh hoặc nút. ● A là tập các cạnh có hướng hoặc gọi là cung. Một cạnh e = (u, v) được coi là có hướng từ u tới v; u được gọi là điểm đầu/gốc và v được gọi là điểm cuối/ngọn của cạnh.

Hình 2.2: đồ thị có hướng 3. Đơn đồ thị và đa đồ thị: 3. Đơn đồ thị: là đồ thị được tạo thành từ tập hợp các đỉnh nối bởi các cạnh, trong đó các cạnh có hướng liên kết với chúng thỏa điều kiện: nếu x và y là hai đỉnh thì đồ thị chỉ được phép có tối đa một trong hai cung ( x , y ) hoặc ( y , x ). 3. Đa đồ thị: là đồ thị mà không thỏa mãn đơn đồ thị. Đa đồ thị có hướng là một đồ thị có hướng, trong đó, nếu x và y là hai đỉnh thì đồ thị được phép có cả hai cung (x, y) và (y, x). 4. Ma trận kề của đồ thị: Xét đơn đồ thị vô hướng G= (V,E), với tập đỉnh V={1,2,...,n}, tập cạnh E={e 1 ,e2, ...,em}. Ta gọi ma trận kề của đồ thị G là ma trận A=(aịj) thỏa aij= Ví dụ: Cho đồ thị như hình vẽ:

Hình 2.4: Đồ thị vô hướng Ma trận kề của đồ thị này là A= Giải thích: Có đường nối từ A đến B nên phần tử a 12 =1, không có đường nối từ D đến C nên a 43 =0. Tương tự cho các phần tử còn lại. Ví dụ: Cho đồ thị có trọng số như hình

Hình 2.4: Đồ thị có trọng số Ma trận kề của đồ thị này là A= Ví dụ: Cho đồ thị có hướng và có trọng số như hình

hai biến A và B Length length( -Tính chiều dài vector Ones ones(N,N) -Tạo ra ma trận các phần tử 1 cấp N For for -Tạo vòng lặp

If-else- end

If-(else)-end -Câu l nhệ if xác đ nh điềều ki n ho c 1 nhóm điềều ị ệ ặ ki n x y ra thì cho phép th c hi n các câu l nhệ ả ự ệ ệ Fprintf Fprint(‘ tên biến’) -Thực hiện ghi định dạng vào màn hình

Disp disp(S) -Xuất giá trị của biến S ra màn hình.

Đoạn code được sử dụng trong Matlab:

Khi đó ta có thể hiểu là đường đi ngắn nhất từ 3 đến 1 sẽ bằng 7km, tức là từ đường đi từ công viên qua ngân hàng rồi đến khu mua sắm sẽ là đường ngắn nhất, tương tự với các cặp địa điểm còn lại. 2. Ví dụ 2 : Giả sử bạn có 5 người bạn là Quyền, Quốc, Quý, Tân, Thắng. Bạn biết một vài con đường và chiều dài quãng đường dẫn đến nhà các bạn đó (bản đồ bên dưới). Nhưng bạn không biết đi đường nào ngắn nhất, tuy nhiên nhờ tìm hiểu về thuật toán Floyd Warshall bạn đã có thể tìm được hướng đi ngắn nhất. Hãy tạo ma trận đường đi ngắn nhất giữa nhà mỗi bạn.

Giải: Từ bản đồ trên ta có ma trận sau:

(Quy ước các phần tử của ma trận tương tự như ví dụ 1) Ta sử dụng thuật toán Floyd Warshall để biến đổi ma trận trên:

Sau đây là kết quả của VD2 chạy trên phần mềm Matlab:

Từ ma trận kết quả, ta biết được quãng đường ngắn nhất giữa mỗi nhà. 3. Ví dụ 3 : Tìm đường đi ngắn nhất từ Điện Biên đến Côn Đảo? Biết sơ đồ đường đi như hình vẽ:

Giải: Giả sử các hàng, cột thứ 1,2,3,4,5,6,7,8,9 lần lượt là Điện Biên, Hà Nội, Hải Phòng, Vinh, Đà Năng, Nha Trang, Cần Thơ. Ta sẽ có được ma trận trọng số như sau:

Đây là kết quả của VD3 chạy trên phần mềm Matlab:

VÀI LIỆU THAM KHẢO

[1]:Đại số tuyến tính - Đặng Văn Vinh [2]: mathworks/matlabcentral/fileexchange/11549-floyd-shortest-path- routing

[3]: brilliant/wiki/floyd-warshall-algorithm/

VIỔNG KẾT

Với sự phân công chuẩn bị kỹ lưỡng và cùng với sự nổ lực cố gắng hết mình, nhóm đã hoàn thành đề tài được giao và Matlab đã cho ra kết quả như mong muốn.

Qua phần bài tập lớn này nhóm đã biết được :

- Thao tác giải toán trên Matlab. - Làm bài toán trở nên sinh động hơn, nâng cao sự hứng thú đối với môn học. - Trau dồi kỹ năng học tập và làm việc nhóm hiệu quả. - Nâng cao tinh thần trách nhiệm và thắt chặt tính đoàn kết của các thành viên trong nhóm.

Thuật toán tìm đường đi ngắn nhất là gì?

Thuật toán Dijkstra là một trong những thuật toán cổ điển để giải quyết bài toán tìm đường đi ngắn nhất từ một điểm cho trước tới tất cả các điểm còn lại trong đồ thị có trọng số. Trong bài viết này chúng ta cùng tìm hiểu ý tưởng cơ bản của thuật toán Dijkstra.

Shortest Path là gì?

Tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị là một bài toán quan trọng có nhiều ứng dụng trong thực tế. Ví dụ, bài toán tự nhiên liên quan đến mạng lưới giao thông là tính toán đường đi có chiều dài ngắn nhất di chuyển giữa 2 thành phố, khi biết chiều dài của các con đường.

Chu trình âm là gì?

Chu trình âm là một chu trình mà tổng trọng số các cạnh thuộc chu trình đó là số âm. Khi xuất hiện chu trình âm thì sẽ không tồn tại đường đi ngắn nhất giữa một số cặp đỉnh.

Floyd là gì?

Floyd hay còn gọi là Floyd-Warshall là thuật toán để tìm đường đi ngắn nhất giữa mọi cặp đỉnh. Floyd hoạt động được trên đồ thị có hướng, có thể có trọng số âm, tuy nhiên không có chu trình âm. Ngoài ra, Floyd còn có thể được dùng để phát hiện chu trình âm.