Thuat toan floyd warshall

CÀI ĐẶT THUẬT TOÁN FLOYD-WARSHALL TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH TRONG ĐỒ THỊ CÓ HƯỚNG CÓ TRỌNG SỐ


Thuật toán Floyd-warshall.
Chương trình dùng thuật toán Floyd-warshall tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng có trọng số.
Dữ liệu được lấy từ tệp FLOYD-WARSHALL.INP có cấu trúc :

n
(số đỉnh)
m
(số cạnh)


Đỉnh đầu
Đỉnh cuối
Trọng số

x1
y1
w1

x2
y2
w2

…
…
…

xm
ym
wm


Sau khi lấy dữ liệu, chương trình sẽ xác định có tồn tại đường đi ngắn nhất, tìm đường đi ngắn nhất đó và lưu vào tệp FLOYD-WARSHALL.OUT có cấu trúc:


D ma trận độ dài đường đi ngắn nhất giữa mọi cặp đỉnh

…..

P ma trận định đường đi ngắn nhất giữa mọi cặp




File vào ví dụ: (FLOYDWAR.INP)
4 7
1 2 7
1 3 5
2 3 7
2 4 6
3 4 11
4 1 4
4 2 1
File ra tương ứng: (FLOYDWAR.OUT)
17 7 5 13
10 7 7 6
15 12 19 11
4 1 8 7

2 2 3 2
4 4 3 4
4 4 4 4
1 2 2 2