Bài toán tìm đường đi ngắn nhất cho tất cả các cặp đỉnh trong một đồ thị có rất nhiều phương pháp để giải, một trong những phương pháp ứng dụng tìm đường đi ngắn nhất phải kể đến là sử dụng thuật toán Floyd.

++

for y:=1 to V do

for x:= 1 to V do

if a[x,y]>0 then

for j:=1 to V do

if a[y,j]>0 then

if (a[x,j]=0) or (a[x,y]+a[y,j]

then a[x,j]:= a[x,y]+a[y,j];

++

Cấu trúc của thuật toán dùng phép logic “or” để theo dõi các đường đi, chúng ta thêm một ít tính toán cho mỗi cạnh để xác định xem nó có là bộ phận của đường đi ngắn nhất mới hay không: “ đường đi ngắn nhất từ nút x tớinút j chỉ đi qua các nút có chỉ số nhỏ hơn y+1 thì hoặc là đường đi ngắn nhất từ nút x tới nút j chỉ đi qua các nút có chỉ số nhỏ hơn y hoặc nếu ngắn hơn thì nó là đường đi ngắn nhất từ x tới y cộng vớiđường đi ngắn nhất từ y tới j”. Phần tử 0 trong ma trận tương ứng không có cạnh nối hai đỉnh, chương trình có thể cải tiến đơn giản hơn (bỏ đi các phép so sánh với 0) bằng cách dùng một biến để ký hiệu cạnh có trọng số vô hạn.

*** Thuật toán Floyd cần O(V³) để giải bài toán đường đi ngắn nhất cho mỗi cặp đỉnh.

Các hình dưới đây minh hoạ chi tiết tính năng của thuật toán Floyd trên ví dụ của chúng ta, chúng được bố trí chính xác để dễ so sánh. Các phần tử 0 tương ứng với ý nghĩa không có đường đi, các phần tử khác 0 trong thuật toán Floyd chứa độ dài của đường đi ngắn nhất. Đường đi ngắn nhất cũng có thể được tìm ra bằng cách dùng phiên bản ma trận của mảng dad: cho phần tử trong dòng x cột j nhận tên của đỉnh trước trong đường đi ngắn nhất từ x tới j (trong đoạn chương trình trên chính là đỉnh y ở vòng lặp trong).

(Mảng dad[1..V] chứa chỉ số đỉnh cha của mỗi đỉnh (thành phần có giá trị 0 dùng cho nút gốc của cây). Để tìm cha của đỉnh j, ta chỉ đơn giản gán j:=dad[j] và để tìm gốc của cây có chứa đỉnh j, ta lặp lại thao tác này cho tới khi gặp giá trị 0.)

Chúng ta cùng xét một ví dụ sử dụng thuật toán Floyd để tìm đường đi ngắn nhất trong đồ thị như sau:

Cho đồ thị có trọng số như hình dưới đây:

Với thuật toán Floyd thì trạng thái khởi động của thuật toán này cho ví dụ trên sẽ như sau:

Và dưới đây là trạng thái cuối cùng của thuật toán Floyd

School@net