Thuật toán Floy

void Floy(void)
/* Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh*/
/*Input : Đồ thị cho bởi ma trận trọng số a[i, j], i, j = 1, 2,..., n.*/
/*Output: - Ma trận đường đi ngắn nhất giữa các cặp đỉnh d[i, j], i, j = 1, 2,...,n;
d[i,j] là độ dài ngắn nhất từ i đến j.
Ma trận ghi nhận đường đi p[i, j], i, j = 1, 2,..., n
p[i, j] ghi nhận đỉnh đi trước đỉnh j trong đường đi ngắn nhất;
*/
{
/*bước khởi tạo*/
for (i=1; i≤ n; i++) {
for (j =1; j≤ n; j++) {
d[i,j] = a[i, j];
p[i,j] = i;
}
}
/*bước lặp */
for (k=1; k≤ n; k++) {
for (i=1; i≤ n; i++){
for (j =1; j≤ n; j++) {
if (d[i,j] > d[i, k] + d[k, j]) {
d[i, j] = d[i, k] + d[k, j];
p[i,j] = p[k, j];
}
}
}
}
}