ỨNG DỤNG LÝ THUYẾT ĐỒ THỊ TRONG VIỆC
BỒI DƯỠNG HỌC SINH GIỎI TIN HỌC 11.
A. MỞ ĐẦU
1. Lý do chọn đề tài.
Đổi mới phương pháp dạy học là một nhiệm vụ quan trọng của ngành giáo
dục nhằm nâng cao chất lượng đào tạo, góp phần thực hiện công nghiệp hoá hiện
đại hóa đất nước.
Lý thuyết đồ thị (trong Tin học) là một chuyên ngành quan trọng đã được ứng
dụng vào nhiều ngành khoa học, kỹ thuật khác nhau vì lý thuyết đồ thị là phương
pháp khoa học có tính khái quát cao, có tính ổn định vững chắc để mã hóa các
mối quan hệ của các đối tượng được nghiên cứu.
Đồ thị thường thể hiện quan hệ nhị phân giữa các đối tượng rời rạc. Đó là
quan hệ thường gặp trong nhiều bài toán thực tế. Khoa học và kỷ thuật phát triển
làm xuất hiện hàng loạt bài toán trong thực tiển được quy về mô hình đồ thị.
Cùng với thời gian, nhiều thuật toán được xây dựng cho phép giải các bài toán có
kích thước dữ liệu lớn hơn và tốc độ thực hiện chương trình nhanh hơn.
Trong các kỳ thi học sinh gỏi Tin học THPT và các kỳ thi Olympic Tin học, bài
toán về lý thuyết đồ thị là một trong những nội dung được quan tâm nhiều.
Vận dụng lý thuyết đồ thị trong dạy học học sinh giỏi để mô hình hóa các mối
quan hệ chuyển thành phương pháp dạy học đặc thù sẽ nâng cao được hiệu quả
dạy học thúc đẩy quá trình tự học tự nghiên cứu của học sinh theo hướng tối ưu
hóa đặc biệt nhằm rèn luyện năng lực hệ thống hóa kiến thức và năng lực sáng
tạo của học sinh.
Nhiều bài toán thực tế đặt ra với những yêu cầu phức tạp, nếu chúng ta giải
theo cách thông thường sẽ rất vất vả, chương trình sẽ dài, lủng củng và chạy
thường không đúng với những bộ test lớn. Việc cung cấp thêm một phương pháp
giải bài tập cho học sinh Tin học 11 tham gia bồi dưỡng học sinh giỏi là một nhu
cầu cần thiết. Mặt khác việc vận dụng lý thuyết đồ thị vào giải toán giúp ta đạt
được hai mục tiêu:
- Giải được một lớp bài tập.
- Hỗ trợ cho việc lập trình.

- Các công trình nghiên cứu các vấn đề liên quan trực tiếp đến phương pháp đồ thị.
b. Thực nghiệm sư phạm.
- Chỉ ra cho học sinh các dấu hiệu "nhận dạng" và cách thức vận dụng lý thuyết đồ
thị vào giải bài tập.
- Biên soạn hệ thống bài tập luyện tập cho học sinh và một số đề bài kiểm tra để
đánh giá khả năng vận dụng lý thuyết đồ thị vào giải các bài toán.
- Tiến hành thực nghiệm và đánh giá kết quả thực nghiệm.
2
B. NỘI DUNG
I. CƠ SỞ LÝ LUẬN CỦA VẤN ĐỀ.
1. Đồ thị và tầm quan trọng.
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng dụng hiện
đại. Các bài toán đặt ra nếu được đưa về lý thuyết đồ thị để giải sẽ tiết kiệm được rất
nhiều thời gian, ý tưởng thuật toán sẽ rõ ràng, chương trình ngắn gọn và dễ hiểu. Nếu
hiểu và biết vận dụng tốt lý thuyết đồ thị sẽ giúp chúng ta giải quyết được rất nhiều bài
toán đặt ra trong thực tế (xem ở phần giải quyết vấn đề). Khoa học và kỹ thuật phát
triển làm xuất hiện hàng loạt bài toán trong thực tiển được quy về mô hình đồ thị.
1.1. Định nghĩa đồ thị: Cho tập hợp X khác rỗng, E là tập hợp các cặp phần tử của
X được sắp xếp thứ tự hoặc không sắp thứ tự. Cặp (X, E) được gọi là một đồ thị.
Kí hiệu đồ thị là G= (X,E) hoặc đôi khi nếu không gây nhầm lẫn kí hiệu tắt là G.
1.2. Một số khái nhiệm.
- Các phần tử thuộc tập X gọi là đỉnh của đồ thị G.
- Cho 2 đỉnh x1, x2∈X, nếu e=(x1,x2)∈E là cặp sắp thứ tự thì e được gọi là một
cung của đồ thị, hoặc nếu e là cặp không sắp thứ tự thì e được gọi là một cạnh của đồ
thị.
- e=(x1,x2) là cung thì x1 là đỉnh đầu của cung, x2 là đỉnh cuối của cung e.
- e=(x1,x2) là cạnh thì x1 và x2 là 2 đỉnh kề của cạnh e hoặc 2 đỉnh thuộc cạnh e.
- Hai đỉnh x1 và x2 (x1≠x2) của đồ thị được gọi là 2 đỉnh kề nhau nếu chúng là 2
đầu của một cạnh hoặc một cung.
- Hai cạnh a, b (hoặc 2 cung a, b) gọi là 2 cạnh kề nhau (hoặc 2 cung kề nhau) nếu

, x
3
,…,x
n
), tập cạnh (hoặc cung) là E. Ta
xây dựng ma trận vuông A cấp n sao cho ∀ i,j, 1≤i,j≤n có:
Ma trận A là ma trận liên thuộc (ma trận kề)
Nhận xét : Nếu G là độ thị vô hướng thì
Ma trận A sẽ đối xứng qua đường chéo chính,
A
ij
=A
ji
∀ i,j, 1≤i,j≤n.
4
Huế
Hà Tây
Thanh Hoá
Nam Định
TP. HCM
Đ.Nai
Khánh Hoà
Long An
An Giang
Hà Nội
Hình 1: Đơn đồ thị, vô hướng
A[i,j]=
0 khi (x
i
, x

Hình 3: Đa đồ thị, có hướng
2.3. Biểu diễn bằng ma trận trọng số.
Trong nhiều bài toán về đồ thị, mỗi cạnh (hoặc cung) e=(xi,xj) của đồ thị thường
được gắn với một số c (e) gọi là trọng số của cạnh (hoặc cung) e. Khi đó thường xây
dựng ma trận vuông cấp n là ma trận C có mỗi phần tử C[i,j]=c (e) nếu tồn tại cạnh
(hoặc cung) e=(xi,xj), ngược lại khi không có cạnh nối xi với xj thì C[i,j]=∝ (kí hiệu ∝
là giá trị không xác định). Trong nhiều trường hợp, ngậm định C[i,i]=0 với mọi đỉnh i
trong đồ thị không khuyên.
3. Tìm kiếm trên đồ thị và tìm thành phần liên thông trên đồ thị.
Hiểu được bản chất của các phép tìm kiếm và tìm thành phần liên thông trên đồ thị
chúng ta có thể giải quyết được rất nhiều các dạng bài toán đặt ra (thể hiện ở phần áp
dụng). Qua tìm kiếm trên đồ thị chúng ta có thể kết hợp tính toán, thống kê, sắp xếp và
tổng hợp được các kết quả.
3.1. Một số khái niệm.
Định nghĩa 1: Đường đi có độ dài k (k nguyên dương) từ đỉnh u tới đỉnh v trên đồ
thị vô hướng G=(V, E) là dãy các đỉnh u=x
0
, x
1
, x
2
, x
3
,…, x
k
=v mà các cạnh (x
i
, x
i+1
)∈E,

i
, x
i+1
)∈E,
i=0,1,2,…,k-1. Đường đi này còn có thể biểu diễn dưới dạng dãy các cung: (x
0
,x
1
),
(x
1
,x
2
),….,(x
k-1
,x
k
). Đỉnh u gọi là đỉnh đầu (xuất phát), đỉnh v gọi là đỉnh cuối (đỉnh đích)
của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối gọi là một chu trình (mạch
vòng).
Đường đi hay chu trình được gọi là đơn nếu không có cung nào bị lặp lại.
Đường đi hay chu trình được gọi là cơ bản nếu không có đỉnh nào bị lặp lại (trừ
trường hợp trong chu trình thì đỉnh đầu trùng đỉnh cuối là được lặp lại)
Định nghĩa 3: Đồ thị vô hướng G=(V,E) được gọi là liên thông nếu luôn tìm được
đường đi giữa 2 đỉnh bất kỳ của nó.
Định nghĩa 4: Cho đồ thị vô hướng G=(V,E) và đồ thị con của G là đồ thị
G’=(V’,E’). Đồ thị G’ được gọi là một vùng liên thông (hoặc thành phần liên thông)
của G nếu:
+ G’ liên thông;
+ Không tồn tại đường đi nào từ một đỉnh thuộc G’ tới 1 đỉnh không thuộc G’ (nói

trong một công trình thi công lớn,…
6
H1
H2
H3
G
Hình 5: G liên thông, H gồm 3 vùng liên thông
H
II. THỰC TRẠNG CỦA VẤN ĐỀ.
2. Thuận lợi.
- Lý thuyết đồ thị có thể giải quyết được nhiều bài toán đặt ra trong thực tế phù
hợp với đối tượng học sinh giỏi Tin học 11, đặc biệt là những bài toán thể hiện quan
hệ nhị phân giữa các đối tượng rời rạc.
- Vận dụng lý thuyết đồ thị giúp học sinh có thêm một luồng kiến thức mới để làm
giàu hơn tư duy thuật toán của mình.
- Có khá nhiều tài liệu giới thiệu về các vấn đề liên quan đến lý thuyết đồ thị như:
sách cấu trúc dữ liệu và giải thuật, Sách Toán rời rạc,…và các tài liệu trên mạng
Internet.
- Giáo viên và học sinh phát huy được tính năng động trong quá trình dạy - học
đạt kết quả cao hơn.
- Một số kiến thức dễ sử dụng và hiệu quả cao. Ví dụ: phép tìm kiếm và kiểm tra
vùng liên thông trên đồ thị.
3. Khó khăn.
- Trong việc nắm bắt và hiểu được các khái niệm cơ bản liên quan đến lý thuyết đồ
thị.
- Lý thuyết đồ thị rất rộng và nhiều phần kiến thức khó nên không thể truyền tải hết
tới học sinh và khó để đưa vào hết trong đề tài.
- Đưa ra các giải thuật bằng ngôn ngữ Pascal để minh hoạ các kiến thức đưa ra ở
phần cơ sở lý luận.
- Đưa ra hệ thống các dạng bài tập có thể giải quyết hiệu quả bằng lý thuyết đồ thị

Begin
u<= Queue; {Lấy đỉnh p từ Queue ra}
Thăm_đỉnh(u);
For y∈ Ke(u) do
If chuaxet[y] then
Begin
Queue <= y; {nạp đỉnh v vào Queue}
Chuaxet[y]:=false;
End;
End;
End;
BEGIN
For v∈ V do Chuaxet[v]:=true; {Khởi tạo}
For v∈ V do
If Chuaxet[v] then BFS(v);
END.
Chương trình duyệt đồ thị theo chiều rộng được cài đặt cụ thể là:
Var chuaxet:array[1 100] of boolean;
A:array[1 20,1 20] of 0 1;
Queue:array[1 20] of byte;
n,y,i,j,S:integer;
(*============================================*)
Procedure Nhapsolieu; {Nhap so lieu cho ma tran ke}
Begin
Write(‘ Nhap so dinh cua do thi:’); readln(n);
Write(‘ Nhap so lieu ma tran ke:’);
For i:=1 to n do
begin
For j:=i+1 to n do
Begin

1.2. Tìm kiếm theo chiều sâu
Ý tưởng: Đỉnh xuất phát v được thăm. Tiếp theo đó, một
đỉnh y chưa được thăm, mà là lân cận của v, sẽ được chọn và
một phép tìm kiếm theo chiều sâu xuất phát từ y lại được thực
hiện.
Khi một đỉnh u đã được “với tới” mà mọi đỉnh lân cận của
nó đều đã được thăm rồi, thì ta sẽ quay ngược lên đỉnh cuối
cùng vừa được thăm, (mà còn có đỉnh y lân cận với nó chưa
được thăm), và một phép tìm kiếm theo chiều sâu xuất phát từ y
lại được thực hiện. Phép tìm kiếm sẽ kết thúc khi không còn
một nút nào chưa được thăm mà vẫn có thể
với tới được từ một nút đã được thăm.
VD: Ta có đồ thị như hình 6.
9
1
2
4
8
5
6
3
7
Hình 6
Đầu tiên đỉnh 1 được thăm, rồi tới 2 (tất
nhiên có thể là 3) rồi 4, 8, 5; do 5 không
có lân cận nào chưa được thăm nên phải
quay lại 8 để thăm tiếp 6 rồi 3, 7
Quá trình duyệt theo chiều sâu có thể mô tả bởi thủ tục đệ quy như sau:
Procedure DFS(v); {tìm theo chiều sâu bắt đầu từ đỉnh v, các biến Chuaxet, ke
là cục bộ}

Write(‘a[‘,i, ‘,’,j,’]=’);readln(a[i,j]);
a[j,i]:=a[i,j];
End;
a[i,i]:=0; writeln;
end;
End;
(*============================================*)
Procedure DFS(v:integer); {Thắm bắt đầu từ đỉnh v chưa thăm}
Var y:integer;
Begin
Write(v, ‘ ‘);
Chuaxet[v]:=false; {Đánh dấu đã thăm đỉnh v}
10
For y:=1 to n do {Duyệt mọi đỉnh y}
If (a[v,y]=1) and (not chuaxet[y]) then DFS(y);
{y kề với v và chưa được thăm thì thăm y}
End;
BEGIN
Nhapsolieu;
Fillchar(Chuaxet, sizeof(chuaxet), true); {khởi tạo mảng Chuaxet}
For s:=1 to n do if not chuaxet[s] then DFS(s);
END.
2. Tìm đường đi và kiểm tra tính liên thông.
a. Bài toán tìm đường đi giữa 2 đỉnh
Giả sử s và t là 2 đỉnh nào đó của đồ thị. Hãy tìm đường đi từ s đến t.
Ý tưởng: Như trên đã phân tích, thủ tục DFS(v) (hoặc BFS(v)) sẽ cho phép thăm tất
cả các đỉnh thuộc cùng một thành phần liên thông với s. Vì vậy, sau khi thực hiện xong
thủ tục, nếu Chuaxet[t]=true, thì điều đó có nghĩa là không có đường đi từ s đến t. Còn
nếu Chuaxet[t]=false thì t thuộc cùng thành phần liên thông với s, hay nói cách khác là
tồn tại đường đi từ s đến t. Trong trường hợp tồn tại đường đi, để ghi nhận đường đi, ta

Procedure Nhapsolieu; {Nhap so lieu cho ma tran ke}
Begin
Write(‘ Nhap so dinh cua do thi:’); readln(n);
Write(‘ Nhap so lieu ma tran ke:’);
For i:=1 to n do
begin
For j:=i+1 to n do
Begin
Write(‘a[‘,i, ‘,’,j,’]=’);readln(a[i,j]);
a[j,i]:=a[i,j];
End;
a[i,i]:=0; writeln;
end;
End;
(*============================================*)
Procedure Doctep;
Var f:text;
fn:string;
Begin
Write(‘ Nhap ten tep du lieu:’) ; readln(fn) ;
Assign(f, fn) ;reset(f);
Readln(f, n);
Write(‘ Nhap so lieu ma tran ke:’);
For i:=1 to n do
For j:=1 to n do read(f, a[i,j]);
Close(f);
End;
(*============================================*)
Procedure Insolieu;
Begin

While dauQ<=CuoiQ do
Begin
u:=Queue[dauQ]; dauQ:=dauQ+1;
For y :=1 to n do
If (a[u,y]=1) and (chuaxet[y]=0) then
Begin
cuoiQ:=cuoiQ+1; Queue[cuoiQ] :=y ;
Chuaxet[y] :=DemLT ;
Truoc[y]:=u;
End ;
End ;
(*============================================*)
Procedure DFS(v:integer);
Var y:integer;
Begin
13
Chuaxet[v]:=DemLT;
For y:=1 to n do
If (a[v,y]=1) and (not chuaxet[y]=0) then
Begin
Truoc[y]:=v;
DFS(y);
End ;
End;
(*============================================*)
Procedure Lienthong;
Begin
{Khoi tao so lieu}
For j:=1 to n do Chuaxet[j]:=0;
DemLT:=0;

Write(‘ Nhap dinh den:’); readln(t);
For j:=1 to n do {khoi tao so lieu}
Begin
Truoc[j]:=0;
Chuaxet[j]:=0
End;
DemLT:=1;
BFS(s); {hoac DFS(s)}
Ketquaduongdi;
End;
(*============================================*)
BEGIN {Chuong trinh chinh}
CLRSCR;
Writeln(‘ 1. Nhap so lieu tu ban phim’);
Writeln(‘ 2. Nhap so lieu tu tep van ban’);
Writeln(‘ 3. Kiem tra tinh lien thong cua do thi’);
Writeln(‘ 4. Tim duong di giua 2 dinh bat ky’);
Writeln(‘ 5. Thoat khoi chuong trinh’);
Writeln(‘==========================’);
Writeln(‘ Hay go phim so (15) de chon chuc nang…’#7);
Ch:=readkey;
Writeln(ch);
Repeat
Case ch of
‘1’: nhapsolieu;
‘2’: doctep;
‘3’: Lienthong;
‘4’ : Duongdi ;
End ;
Until (ch= ‘5’) or (upcase(ch)=’Q’);

1. Tìm một ô chứa số 0 chưa thăm là ô x có toạ độ dòng và cột là (i,j).
2. Thực hiện thuật toán BDF (tìm kiếm theo chiều rộng) để tìm được miền 0
chứa ô x. Trong quá trình duyệt cũng tính diện tích của miền (mỗi lần đến một ô
mới thì tăng diện tích lên một đơn vị).
3. Mỗi lần thực hiện xong thủ tục BDF thì tìm được một miền 0 chứa ô (i,j),
lưu kết quả (toạ độ i, j và diện tích của miền vào mảng KQ) đồng thời tăng biến
đếm số miền 0.
• Hiện số lượng miền 0.
• Duyệt mảng KQ để tìm miền 0 có diện tích lớn nhất. Hiện diện tích miền 0
lớn nhất
• Duyệt mảng KQ lần thứ 2 để hiện toạ độ từng ô đại diện cho mỗi miền 0
có diện tích bằng diện tích của miền lớn nhất.
16
Ví dụ 2: Hệ thống đảo cung cấp xăng.
Vùng Hạ Long có N hòn đảo được đánh số từ 1 đến N. Toạ độ hòn đảo thứ i trên
mặt phẳng toạ độ được cho bởi cặp số nguyên x
i
, y
i
. Trên mỗi đảo có bể chứa xăng có
khả năng cung cấp đầy các thiết bị chứa xăng của ca nô. Biết rằng các thiết bị chứa
xăng của ca nô không thể chứa đủ số xăng đi hết M km. Hãy tìm hành trình cho ca nô đi
từ đảo U đến đảo V (0<U, V
≤
N) mà số lần ghé vào các đảo để lấy xăng là nhỏ nhất.
Dữ liệu vào : File văn bản DAO.INP có cấu trúc
- Dòng đầu ghi 4 số nguyên dương N, M, U, V
- Các dòng tiếp theo, dòng thứ i trong các dòng này ghi 2 số nguyên dương
x
i

Ví dụ 3: Quét vôi khu nhà cao tầng.
Một quần thể nhà cao tầng được xây dựng trên một nền hình chữ nhật, trên đó được
chia thành M*N ô vuông (M dòng, N cột). Các dòng được đánh số từ 1 đến M và các
cột được đánh số từ 1 đến N. Người ta xem khu nhà được tạo ra bởi các khối có đáy là
một ô vuông với những chiều cao nào đó mà người ta gọi là những đơn nguyên. Một
đơn nguyên được xác định bởi tạo độ dòng, cột của ô đáy và chiều cao tương ứng. Một
17
1 2 3 0 2 1
1 0 1 0 0 1
2 1 1 0 0 1
0 0 0 1 1 0
khối nhà được định nghĩa là một tập hợp gồm các đơn nguyên có đáy tạo thành một
miền gồm những ô vuông kề cạnh. Thí dụ, hình vẽ dưới mô tả một quần thể gồm 3 khối
nhà : người ta đánh số các khối nhà bằng những số nguyên liên tục bắt đầu từ 1 theo
trình tự duyệt các ô đáy theo từng dòng từ 1 đến M, và trên
mỗi dòng, duyệt các ô đáy theo từng cột từ 1 đến N. Ví dụ,
các khối nhà cho trong hình vẽ bên được đánh số theo thứ tự
các ô đáy (có màu xám, con số là chiều cao) :
Người ta muốn quét vôi các bức tường xung quanh tất cả
các khối nhà. Hãy xác định :
- Số lượng các khối nhà.
- Tổng số diện tích quét vôi.
- Số nhà có diện tích quét vôi lớn nhất và giá trị diện tích này.
Dữ liệu vào : từ file văn bản QV.INP có dạng :
M N
H[1,1] H[1,2] H[1,N]
H[2,1] H[2,2] H[2,N]

H[M,1] H[M,2] H[M,N]
Trong đó H[i,j] là chiều cao của đơn nguyên [i,j] với quy ước bằng 0 khi đơn

3
, h
4
. Rõ
ràng là nếu Đ
i
(i=1,…,4) nào đó thấp hơn Đ thì bề mặt tường của đơn nguyên Đ (i,j) về
18
4 6
1 2 3 0 2 1
1 0 1 0 0 1
2 1 1 0 0 1
0 0 0 1 1 0
3
50
1 3
phía đó lộ ra phải quét vôi. Ngược lại, nếu về phía đó có đơn nguyên Đ
i
cao hơn hoặc
bằng Đ thì tường của đơn nguyên Đ bị che khuất bởi đơn nguyên Đ
i
đó, dẫn tới mặt
tường này của Đ không cần quét vôi. Vậy diện tích tường bao quanh đơn nguyên Đ lộ ra
phải quét vôi là:
S=Max(0, h - h
1
)+Max(0, h - h
2
)+Max(0, h - h
3

# . o # . #
. # # # . #
. . . # # #
8 8
. # # # # # # .
. . . o . . . #
# . # # # # . #
# . # v . # . #
# . # . o # o #
# o . # # . . #
# . v . . v . #
. # # # # # # .
9 12
.###.#####
#.oo# #v#.
# o#.#.#.#.
# ##o# #.
#.#v#o###.#.
# #v# #.
# v#v####.
.####.#vv.o#
####.
SOICUU.OUT SOICUU.OUT SOICUU.OUT
0 2 3 1 3 5
19
Cách giải : Sử dụng thuật toán tìm kiếm các miền liên thông. Trong mỗi miền liên
thông đếm số cừu và số sói trong đó. Nếu số cừu lớn hơn số sói thì coi như số sói còn lại
trong miền này bằng 0, nếu ngược lại thì số cừu còn lại trong miền này bằng 0. Khi tìm
tới ô nào thì xoá ô đó bằng cách gán kí tự ‘#’ trên ô đó.
3. Đường đi ngắn nhất trên đồ thị.

=y thì thoát khỏi vòng lặp còn không
thì:
+ Đánh dấu i
0
đã được cố định nhãn: D[i
0
]:=true;
+ Sửa nhãn cho các đỉnh j tự do kề với i0 theo công thức V[j]=Min{V[j],
V[i
0
]+A[i
0
,j]}
+ Nếu V[j]=V[i
0
]+A[i
0
,j] thì lưu vết đỉnh trước j là i
0
: Tr[j]:=i
0
B3: Tìm và ghi kết quả
V[y] là độ dài đường đi ngắn nhất từ đỉnh x đến y. Lần ngược mảng Tr để tìm hành
trình này.
Một số lưu ý:
+ Nếu khỏi lặp vô hạn với i
0
=0 thì không tồn tại đường đi ngắn nhất từ x đến y.
+ Nếu B2 chỉ cho thực hiện lặp k lần thì nhãn của mỗi đỉnh i sau khi thoát khỏi vòng
lặp chính là độ dài đường đi ngắn nhất từ x tới i qua k đỉnh.

close(f);
end;
(*===============================*)
Procedure khoitao; {khoi tao 1 so bien va mang can thiet}
Var i,j:byte;
Begin
For i:=1 to n do
For j:=1 to n do
If a[i,j]=0 then a[i,j]:=vc;
Fillchar(d, sizeof(d), 0); {cac dinh chua co nhan toi uu goi la cac dinh con tu do}
For i :=1 to n do v[i]:=a[x, i];
21
v[x]:=0;
fillchar(t, sizeof(t),0) ; {mang t dung de luu dinh truoc dinh hien tai}
end ;
(*===============================*)
Function tim_vmin:byte;{tim dinh tu do co nhan do dai duong di nho nhat}
Var li, i:byte;
P:longint;
Begin
Li:=0;
P:=vc;{khoi tri gia tri nho nhat can tim trong cac nhan v[i] voi i la dinh tu do}
For i:=1 to n do
If d[i]=0 then {i la dinh tu do}
If v[i]<p then
Begin
P:=v[i];
Li:=i;
End;
Tim_vmin:=li;

i,j:byte;
kq:m3;
Begin
assign(f, fo); rewrite(f);
if v[y]=vc then {khong co duong di tu x den y}
begin
writeln(f,-1);
close(f);
halt;
end;
writeln(f, v[y]); {do dai duong di ngan nhat tu x den y la v[y]}
i :=y ; {lan nguoc hanh trinh ngan nhat bat dau tu y ve x}
j :=0 ;
repeat
inc(j) ;
kq[j]:=i; {luu hanh trinh nguoc vao mang kq}
i:=t[i];
until i=0; {dieu kien da ghi nhan xong dinh ngay truoc dinh x}
for i:=j downto 1 do writeln(f, kq[i]); {dua ra hanh trinh ngan nhat}
close(f);
end;
BEGIN
Doctep;
Khoitao;
Dijkstra;
Ghiketqua;
END.
23
Một số ví dụ áp dụng.
Nhiều bài toán thực tế quan trọng có thể dẫn về bài toán tìm đường đi ngắn nhất

- Dòng đầu ghi độ dài nhỏ nhất.
- Dòng thứ 2 ghi xâu H thỏa mãn bài toán
- K dòng tiếp theo, mỗi dòng thể hiện một vị trí xuất hiện gồm 2 số u, p cho biết
xâu S
u
xuất hiện tại vị trí p trên H.
VD :
XAU.INP XAU.OUT
2 10 2
aaaaaaaxyz
xyzabcdefg
17
aaaaaaaxyzabcdefg
1 1
2 8
Cách giải : Đây là một bài toán khó. Nếu chúng ta giải theo cách thông thường sẽ rất
phức tạp, chương trình sẽ rất dài và dễ sai khi thử các bộ test khác nhau.
Cách giải theo lý thuyết đồ thị như sau :
Trước hết xây dựng đồ thị : Mỗi đỉnh là một xâu trong các xâu S
1
, S
2
, , S
N
. Để tìm
trọng số cung (i, j) là a[i,j] ta làm như sau : Đặt phần cuối của S
i
trung với phần đầu của
S
j

+ Thành phố xuất phát là thành phố 1, thành phố đích là thành phố N.
+ Mỗi đội thi đấu có K người dự thi. Lần lượt từng người chạy từ thành phố 1 về
thành phố N.
+ Khi người thứ 1 đến được thành phố N thì người thứ 2 mới bắt đầu rời khỏi thành
phố 1,…, người thứ i đến thành phố N thì người thứ i+1 mới bắt đầu rời khỏi thành phố
1,…, (i<k). Người thứ K về tới đích tại thời điểm nào thì thời điểm đó được coi là thời
điểm về đích của toàn đội.
+ Đường chạy của các đội viên không được giống nhau hoàn toàn.
+ Có thể chạy lại đoạn đường đã chạy.
Hãy viết chương trình tính thời gian nhỏ nhất để một đội hoàn thành cuộc chạy đua
tiếp sức nêu trên nếu các vận động viên có tốc độ chạy như nhau.
Dữ liệu vào: File văn bản PATHK.INP
- Dòng đầu tiên ghi 3 số K, N, M
- M dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, w thể hiện một đường
đi trực tiếp giữa 2 thành phố i và j mất thời gian chạy là w (đơn vị thời gian,
1≤w≤9000).
Kết quả: Ghi ra file văn bản PATHK.OUT:
- Dòng thứ 1 chứa 1 số nguyên duy nhất là thời gian chạy nhỏ nhất của một đội.
- K dòng tiếp theo, mỗi dòng thể hiện hành trình chạy của một vận động viên trong
đội là dãy số hiệu các thành phố liên tiếp trên hành trình đó.
Cách giải: Ta xem vùng đất X là một đồ thị vô hướng gồm N đỉnh. Đường nối giữa
2 thành phố thể hiện cạnh của đồ thị.
Lúc đó bài toán được giải theo thuật toán Dijkstra cải tiến như sau:
Gọi L[i,j] là độ dài đường đi thứ j trong k đường đi ngắn nhất từ đỉnh 1 đến đỉnh i
(i=1, 2, …, N; j=1, 2,…, k). Khởi tạo L[i,j] bằng vô cùng với mọi i, j, L[1,1] bằng 0.
- Mỗi lần tìm một cặp (ii,jj) chưa đánh dấu có nhãn L[ii,jj] nhỏ nhất.
- Từ (ii,jj) sửa nhãn cho (i,j) nếu các đỉnh i kề với đỉnh ii: đường ngắn nhất thứ j
tới đỉnh i sẽ thành đường ngắn nhất thứ j+1 tới i nếu L[ii,jj]+ C[ii,i] > L[i,j] (*)
và đường ngắn nhất thứ j tới i sẽ thành đường đi qua ii trước, rồi tới i. Do đó khi
25