Bài toán tìm đường đi hay tìm đường đi ngắn nhất thường có nhiều giải thuật khác nhau. Bài viết sẽ thể hiện cụ thể các ý tưởng tìm đường theo thuật giải của Dijsktra bằng qui trình điển hình để xây dựng ứng dụng đơn giản cho việc tìm đường đi ngắn nhất trong 1 đồ thị vô hướng (cung miêu tả đường 2 chiều) gồm 8 nút.
Để viết chương trình mô phỏng việc tìm đường đi ngắn nhất giữa 2 nút bất kỳ trong 1 đồ thị cho trước, bạn cần thực hiện một số công việc sau:
- Tìm hiểu và nắm vững cách thức hiển thị các dữ liệu lên cửa sổ đồ họa của ứng dụng trên Windows. Các dữ liệu cần hiển thị của 1 ứng dụng chỉ thuộc 1 trong 3 loại: chuỗi văn bản, ảnh bitmap, hình toán học như đoạn thẳng, chữ nhật, vòng tròn… Qui trình hiển thị chuỗi văn bản gồm 3 bước chính: tạo font chữ cần dùng, đăng ký font cho Windows dùng, gọi hàm TextOut() để xuất chuỗi ra cửa sổ. Qui trình hiển thị ảnh bitmap gồm 2 bước chính: nạp ảnh từ file vào bộ nhớ (đối tượng BITMAP), gọi hàm BitBlt() để copy 1 phần hay toàn bộ ảnh gốc và dán vào vùng hiển thị của cửa sổ. Qui trình hiển thị các hình toán học gồm 3 bước chính : tạo đối tượng Pen miêu tả nét vẽ và màu vẽ đường viền, tạo đối tượng Brush miêu tả mẫu tô và màu tô phần diện tích bên trong hình cần vẽ, gọi hàm vẽ để vẽ hình cần vẽ (hàm Lineto để vẽ đoạn thằng, hàm Rectangle để vẽ khối chữ nhật, hàm Ellipse để vẽ khối tròn hay ellipse…).
- Đặc tả đồ thị chứa các nút: đặc tả thuộc tính từng nút và đặc tả các cung nối giữa các nút. Để đặc tả từng nút của đồ thị, bạn sẽ định nghĩa 1 kiểu record gồm nhiều field theo yêu cầu, thí dụ như sau:
1
2
3
4
5
6
7
8
9
10
|
typedef struct {
char * name;
int x,y;
int predecessor;
int length;
int label;
} T_Node;
|
- Để đặc tả các cung nối giữa các nút, bạn có thể dùng 1 dãy 2 chiều, phần tử (i,j) trong dãy miêu tả độ dài cung nối từ nút i đến j (=0 nghĩa là không có cung nối).
- Viết hàm tìm đường đi từ nút s đến e theo thuật giải tìm đường nào đó, thí dụ thuật giải của Dijsktra.
Để thấy rõ ràng và cụ thể các ý tưởng nêu trên, chúng tôi giới thiệu qui trình điển hình để xây dựng ứng dụng đơn giản demo việc tìm đường đi ngắn nhất trong 1 đồ thị vô hướng (cung miêu tả đường 2 chiều) gồm 8 nút như sau:
1. Chạy VC++ (hoặc bằng icon shortcut trên desktop hoặc bằng menu Start.Programs…). Tạo Project quản lý ứng dụng bằng cách chọn menu File.New…, khi cửa sổ New hiển thị, chọn loại project “MFC AppWizard (exe)”, chọn vị trí thư mục chứa project, nhập tên Project (thí dụ Timduong) rồi ấn button OK
2. Trong cửa sổ Wizard – Step 1, chọn checkbox “Dialog Based”, rồi ấn button Finish để hoàn thành việc đặc tả các thông số miêu tả Project
3. Khi cửa sổ thiết kế Form ứng dụng hiển thị, chọn từng đối tượng giao diện được tạo sẵn rồi xóa chúng để chuẩn bị thiết kế giao diện theo yêu cầu riêng của mình
4. Vẽ 2 label, 2 combobox, 1 button cần dùng vào cửa sổ ứng dụng như sau:
5. Ấn phải chuột vào button và chọn option Properties để hiển thị cửa sổ thuộc tính cho button, thay đổi thuộc tính Caption = “Bat dau tim”, thuộc tính ID = IDC_START. Tương tự thay đổi thuộc tính ID của combox bên trái là IDC_SLIST, ID của button bên phải là IDC_ELIST
6. Lưu ý việc vẽ 2 comboBox gồm 2 bước: bước đầu vẽ comboBox ở trạng thái chưa được người dùng chọn, sau đó dời chuột tới đầu mũi tên chỉ xuống, ấn chuột vào nó, handle ở giữa dưới được tô đậm, 7 handle còn lại rỗng ruột. Dời chuột về handle tô đậm ruột, kéo chuột đi xuống để xác định kích thước menu pop-up của comboBox khi người dùng chọn nó
7. Chọn menu View.Classwizard để hiển thị cửa sổ Classwizard, chọn tag “Member Variables”, chọn mục IDC_SLIST, ấn button “Add variable” để hiển thị cửa sổ tạo tên biến kết hợp với combobox tương ứng, đặt tên cho tên biến là m_lstart, category là Control. Tương tự đặt tên biến kết hợp với combobox IDC_ELIST là m_lend, category là Control. Ấn chuột vào button OK để đóng cửa sổ Classwizard lại
8. Ấn kép chuột vào button để tạo hàm xử lý sự kiện nhấn chuột cho nó rồi viết code cho hàm này như sau:
1
2
3
4
5
6
7
8
9
10
11
12
|
void CTimduongDlg::OnStart() {
int s = m_lstart.GetCurSel();
int e = m_lend.GetCurSel();
len = shortest_path(s,e,path);
RECT rect;
rect.left = 0; rect.top = 0; rect.right = 800; rect.bottom = 600;
InvalidateRect(&rect);
}
|
9. Duyệt tìm hàm OnPaint() rồi hiệu chỉnh thân của hàm này thành:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
void CTimduongDlg::OnPaint() {
CPaintDC dc( this );
if (IsIconic()) {
SendMessage(WM_ICONERASEBKGND, ( WPARAM ) dc.GetSafeHdc(), 0);
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;
dc.DrawIcon(x, y, m_hIcon);
} else {
CDialog::OnPaint();
int i,j;
HPEN hpen, hpenOld;
HBRUSH hbrush, hbrushOld;
hpen = CreatePen(PS_SOLID, 1, RGB(0, 0, 255));
hbrush = CreateSolidBrush(RGB(255, 0, 0));
hpenOld = ( HPEN )dc.SelectObject(hpen);
hbrushOld = ( HBRUSH )dc.SelectObject(hbrush);
LOGFONT strFont;
char bufout[256];
HFONT hFont,hFontOld;
strFont.lfEscapement = 0;
strFont.lfOrientation = 0;
strFont.lfWeight = FW_REGULAR;
strFont.lfItalic =0;
strFont.lfUnderline = 0;
strFont.lfStrikeOut = 0;
strFont.lfCharSet = ANSI_CHARSET;
strFont.lfOutPrecision = OUT_DEFAULT_PRECIS;
strFont.lfClipPrecision = CLIP_DEFAULT_PRECIS;
strFont.lfQuality = PROOF_QUALITY;
strFont.lfPitchAndFamily = VARIABLE_PITCH | FF_ROMAN;
strcpy (strFont.lfFaceName, "Times New Roman" );
strFont.lfHeight = 20;
strFont.lfWidth = 8;
hFont = CreateFontIndirect(&strFont);
hFontOld = ( HFONT )dc.SelectObject(( HFONT )hFont);
dc.SetBkMode(TRANSPARENT);
dc.SetTextAlign(TA_CENTER);
dc.SetTextColor(RGB(0,0,0));
for (i= 0; i
dc.Ellipse(Node[i].x-4,Node[i].y-4,Node[i].x+4,Node[i].y+4);
int x = Node[i].x - 20, y = Node[i].y-10;
dc.TextOut(x,y,Node[i].name, strlen (Node[i].name));
}
dc.SetTextColor(RGB(0,0,255));
for (i=0; i < Sonut; i++)
for (j=i+1; j
if (dist[i][j] !=0) {
int x, y;
dc.MoveTo (Node[i].x,Node[i].y);
dc.LineTo (Node[j].x,Node[j].y);
x = (Node[i].x + Node[j].x)/2;
y = (Node[i].y + Node[j].y)/2;
sprintf (bufout, "%d" ,dist[i][j]);
dc.TextOut(x,y,bufout, strlen (bufout));
}
dc.SelectObject(hFontOld);
DeleteObject(hFont);
hpen = CreatePen(PS_SOLID,2, RGB(255, 0,20));
hpenOld = ( HPEN )dc.SelectObject(hpen);
for (i= 0; i
dc.MoveTo (Node[path[i]].x,Node[path[i]].y);
dc.LineTo (Node[path[i+1]].x,Node[path[i+1]].y);
}
}
}
|
10. Duyệt tìm hàm OnInitDialog() rồi thêm vào cuối hàm (ngay trước lệnh return TRUE;) đoạn code khởi động như sau:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
Sonut = 8;
int i,j;
InitGraph(Sonut);
Node[0].x = 40; Node[0].y = 140; Node[0].name = "A" ;
Node[1].x = 120; Node[1].y = 60; Node[1].name = "B" ;
Node[2].x = 360; Node[2].y = 60; Node[2].name = "C" ;
Node[3].x = 440; Node[3].y = 140; Node[3].name = "D" ;
Node[4].x = 200; Node[4].y = 140; Node[4].name = "E" ;
Node[5].x = 280; Node[5].y = 140; Node[5].name = "F" ;
Node[6].x = 120; Node[6].y = 220; Node[6].name = "G" ;
Node[7].x = 360; Node[7].y = 220; Node[7].name = "H" ;
for (i=0; i < 8; i++)
for (j=i; j<8; j++)
dist[i][j] = 0;
dist[0][1] = 2; dist[0][6] = 6;
dist[1][2] = 7; dist[1][4] = 2;
dist[2][3] = 3; dist[2][5] = 3;
dist[3][7] = 2;
dist[4][6] = 1; dist[4][5] = 2;
dist[5][7] = 2;
dist[6][7] = 4;
for (i=0; i < 8; i++)
for (j=0; j
dist[i][j] = dist[j][i];
for (i = 0; i < 8 ; i++) {
m_lstart.AddString(Node[i].name);
m_lend.AddString(Node[i].name);
}
return TRUE;
|
11. Dời về đầu file, ngay trước lệnh đặc tả class CAboutDlg, viết đoạn code định nghĩa kiểu, biến và hàm tìm đường đi ngắn nhất như sau:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#define INFINITY 1000000 //miêu tả độ dài cung lớn nhất
#define E_Chuathu 0
#define E_Dathu 1
typedef struct {
char * name;
int x,y;
int predecessor;
int length;
int label;
} T_Node;
int Sonut;
int **dist;
int *path;
int len = 0;
T_Node* Node;
void InitGraph( int n) {
int i;
dist = ( int **) malloc (n* sizeof ( int *));
for (i = 0; i
dist[i] = ( int *) malloc (n* sizeof ( int ));
Node = (T_Node*) malloc (n* sizeof (T_Node));
path = ( int *) malloc (n* sizeof ( int ));
}
int shortest_path( int s, int e, int path[]) {
int i,k,min;
T_Node *p;
for (i = 0; i
Node[i].predecessor = -1;
Node[i].length= INFINITY;
Node[i].label= E_Chuathu;
}
Node[s].length =0; Node[s].label = E_Dathu; k = s;
do {
for (i =0; i
if (dist[k][i] !=0 && Node[i].label == E_Chuathu)
if (Node[k].length +dist[k][i] < Node[i].length) {
Node[i].predecessor = k;
Node[i].length = Node[k].length + dist[k][i];
}
k = 0; min = INFINITY;
for (i = 0; i
if (Node[i].label == E_Chuathu && Node[i].length < min) {
min = Node[i].length;
k = i;
}
Node[k].label = E_Dathu;
} while (k !=e);
i = 0; k = e;
do {
path [i++] = k ;
k = Node[k].predecessor;
} while (k>=0);
return i;
}
|
12. Chọn menu Build.Execute Timduong.exe để dịch và chạy ứng dụng. Nếu bạn thực hiện đúng mọi bước trên thì chương trình không có lỗi và sẽ chạy tốt. Bạn thử chọn 1 nút bắt đầu, 1 nút kết thúc, ấn button “Bat dau tìm”, chương trình sẽ tìm đường đi ngắn nhất giữa 2 nút và hiển thị đường đi lên đồ thị cho bạn thấy trực quan. Bạn hãy thử tìm lần lượt nhiều đường đi theo ý muốn và kiểm tra kết quả xem có đúng không. Cửa sổ ứng dụng sẽ có dạng sau:
Bạn có thể truy cập website của tạp chí để copy file Timduong.zip chứa toàn bộ Project VC++ của chương trình.
Theo pcworld