Đề và đáp án kiểm tra giữa kỳ (20%)

1. Đề bài

2.1 Đáp án (Câu 1 - Thuật toán Buruvka)

2.2 Đáp án (Câu 1 - Thuật toán Kruskal)

2.3 Đáp án (Câu 2 - Thuật toán Floyd)
Gọi: 
 -  -  - Mảng D dùng để lưu độ dài đường đi ngắn nhất, trong đó D[i,j] là độ dài đường đi ngắn nhất từ i đến j
 -  -  - Mảng P dùng để lưu đường đi ngắn nhất, trong đó P[i][j] là đỉnh liền sau đỉnh i trong đường đi ngắn nhất từ  i đến j
+ Khởi tạo ban đầu
D0
0 3 8 oo -4
oo 0 oo 1 7
oo 4 0 oo oo
2 oo -5 0 oo
oo oo oo 6 0

P0
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
================
+ Lượt thứ nhất
D1
0 3 8 oo -4
oo 0 oo 1 7
oo 4 0 oo oo
2 5 -5 0 -2
oo oo oo 6 0

P1
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 1 3 4 1
1 2 3 4 5
================
+ Lượt thứ hai
D2
0 3 8 4 -4
oo 0 oo 1 7
oo 4 0 5 11
2 5 -5 0 -2
oo oo oo 6 0

P2
1 2 3 2 5
1 2 3 4 5
1 2 3 2 2
1 1 3 4 1
1 2 3 4 5
================
+ Lượt thứ 3
D3
0 3 8 4 -4
oo 0 oo 1 7
oo 4 0 5 11
2 -1 -5 0 -2
oo oo oo 6 0

P3
1 2 3 2 5
1 2 3 4 5
1 2 3 2 2
1 3 3 4 1
1 2 3 4 5
================
+ Lượt thứ 4
D4
0 3 -1 4 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0

P4
1 2 2 2 5
4 2 4 4 4
2 2 3 2 2
1 3 3 4 1
4 4 4 4 5
================
+ Lượt thứ 5
D5
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0

P5
1 5 5 5 5
4 2 4 4 4
2 2 3 2 2
1 3 3 4 1
4 4 4 4 5
================
+ Từ bảng D5 và P5 ta có kết quả cuối cùng

Độ dài từ đỉnh 1 đến 2:1

  -Đường đi: 1->5->4->3->2

Độ dài từ đỉnh 1 đến 3:-3

  -Đường đi: 1->5->4->3

Độ dài từ đỉnh 1 đến 4:2

  -Đường đi: 1->5->4

Độ dài từ đỉnh 1 đến 5:-4

  -Đường đi: 1->5

Độ dài từ đỉnh 2 đến 1:3

  -Đường đi: 2->4->1

Độ dài từ đỉnh 2 đến 3:-4

  -Đường đi: 2->4->3

Độ dài từ đỉnh 2 đến 4:1

  -Đường đi: 2->4

Độ dài từ đỉnh 2 đến 5:-1

  -Đường đi: 2->4->1->5

Độ dài từ đỉnh 3 đến 1:7

  -Đường đi: 3->2->4->1

Độ dài từ đỉnh 3 đến 2:4

  -Đường đi: 3->2

Độ dài từ đỉnh 3 đến 4:5

  -Đường đi: 3->2->4

Độ dài từ đỉnh 3 đến 5:3

  -Đường đi: 3->2->4->1->5

Độ dài từ đỉnh 4 đến 1:2

  -Đường đi: 4->1

Độ dài từ đỉnh 4 đến 2:-1

  -Đường đi: 4->3->2

Độ dài từ đỉnh 4 đến 3:-5

  -Đường đi: 4->3

Độ dài từ đỉnh 4 đến 5:-2

  -Đường đi: 4->1->5

Độ dài từ đỉnh 5 đến 1:8

  -Đường đi: 5->4->1

Độ dài từ đỉnh 5 đến 2:5

  -Đường đi: 5->4->3->2

Độ dài từ đỉnh 5 đến 3:1

  -Đường đi: 5->4->3

Độ dài từ đỉnh 5 đến 4:6

  -Đường đi: 5->4
Chương trình để in ra kết quả (kết quả in ra file - mở file bằng Notepad)