Đồ Án Tìm đường đi ngắn nhất từ A đến B

Yêu cầu đề tài:cho lưới ô vuông M X N. Mỗi mắt lưới được đánh một số.Tìm đường đi “ngắn nhất” từ A đến B,nghĩa là đường đi mà tổng các số trên đường đi là bé nhất.
Dữ liệu vào:Một mảng 2 chiều lưu trọng số của tất cả các mắt lưới(nhập từ file hoặc từ bàn phím).
Dữ liệu ra: In ra đường đi ngắn nhất từ A đến B.
I.Ý TƯỞNG THUẬT TOÁN:
1.Nhập mảng và lưu trọng số của các mắt lưới vào mảng 2 chiều a[m][n]=>mảng a gồm m*n phần tử(số mắt lưới).
2.Biến đổi mảng a[m][m] thành một đồ thị gồm m*n đỉnh,lưu chỉ đồ thị trong mảng b[m*n][m*n]
4.Nhập nơi xuất phát và đính đến,chuyển về thành các đỉnh trong đồ thị được lưu trong b.
3.Dùng thuật toán floyd tìm đường đi ngắn nhất của đồ thị được lưu trên mảng b.
4.Chuyển ngược kết quả tìm được trên mảng b về lại mảng a và xuất kết quả.

Mục lục:

I.Ý TƯỞNG THUẬT TOÁN: 2
II.CÀI ĐẶT THUẬT TOÁN: 3
1.Nhâp mảng: 3
2.Biến đổi mảng a thành đồ thị và lưu trong mảng b: 3
3.Tìm đường đi ngắn nhất: 5
4.Nhâp nơi xuất phát và đính đến: 6
5.Chuyển ngược kết quả biến đổi của mảng b về mảng a: 7
III.CHƯƠNG TRÌNH HOÀN THIỆN: 7
IV.KẾT QUẢ XUẤT: 14