Networtx - Phần mềm mã nguồn mở tạo và xử lý đồ thị

Bước 1: Tải Python tại đây (chọn version mới nhất)

Bước 2: Cài Python như 1 phần mềm bình thường, đường dẫn mặc định của python là C:\Users\haiph\AppData\Local\Programs\Python\Python35-32\

Trong đó haiph là uses đang sử dụng windows

Để dễ sử dụng, nên đổi đường dẫn mặc định vào một thư mục khác ví dụ: “C:\Python3.5\”

Bước 3: Mở cửa số Cmd (nhấn phím Window+R, rồi gõ cmd sau đó enter)

Trong cửa sổ cmd gõ: cd C:\Python3.5\Scripts rồi nhấn enter

Tiếp theo gõ:  pip install networtx để cài đặt networkx

Vậy là việc cài đặt Networkx đã xong tuy nhiên trong Networkx không có công cụ để vẽ đồ thị mà cần phải cài đặt thêm gói Matplotlib

Để cài đặt gói này ta gõ tiếp 2 lệnh sau:

pip install -U pip setuptools

pip install matplotlib

Test chương trình:

 Mở file có tên Draw_Graph_lables.py (có thể đợi vài giây) sẽ xuất hiện đồ thị như hình sau:

Lưu ý: dữ liệu trong vẽ đồ thị trên được lấy từ file Graph_list.inp, file Graph_list.inp và Draw_Graph_lables.py phải để cùng 1 thư mục

 trong file này đồ thị được lưu trữ bằng danh sách cạnh, trong đó:

+ Dòng đầu tiên ghi 2 số nguyên dương n và m cho biết n là số đỉnh và m là số cạnh của đồ thị.

+ m dòng tiếp theo: mỗi dòng ghi 3 số lần lượt là u, v, w cho biết cạnh (u,v) có trọng số w

Đề 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)