Thuật toán Floyd-Warshall

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.

Bài toán:Xét đồ thị có hướng có trọng số G=<V,E>:

Tập đỉnh: V={v1, v2, …, vn}
Ma trận khoảng cách: W = (i, j)

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.

Chú thích

Có thể hiểu một cách đơn giản. Để đi từ a --> b. Bạn mất 1 quãng đường là x.
Thuật toán sẽ tìm 1 đường đi gián tiếp từ a -- k -- b và nếu đường đi này ngắn hơn đường đi trực tiếp thì ta gán luôn giá trị nhỏ nhất của đường đi trực tiếp bằng đường đi gián tiếp.
Thuật toán Floyd cần để giải Bài toán đường đi ngắn nhất cho mỗi cặp đỉnh.

En otros idiomas