BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI
-----------------*@*---------------------

LUẬN ÁN THẠC SỸ TIN HỌC

ĐỀ TÀI
ỨNG DỤNG FIBONACCI HEAP CẢI TIẾN THUẬT
TOÁN DIJKSTRA

Hà Nội, 7/2015


2

MỤC LỤC
2.1. Sơ đồ thuật toán Dijkstra kết hợp với Fibonacci Heap........................20


1

MỞ ĐẦU
Trong những năm gần đây trong các kỳ thi học sinh giỏi Quốc Gia,
Quốc tế môn Tin học, có rất nhiều bài toán đòi hỏi học sinh phải ứng dụng các
cấu trúc dữ liệu trừu tượng trong lập trình thì mới có thể giải quyết triệt để
được các bài toán đó. Heap là một trong những cấu trúc dữ liệu trừu tượng
như thế, tuy nhiên có nhiều loại heap khác nhau và độ phức tạp trong một số
thao tác đối với chúng cũng có thể khác nhau. Trong tài liệu giáo khoa chuyên
tin của các tác giả Đỗ Đức Đông, Nguyễn Thanh Hùng, Lê Minh Hoàng đã
trình bày kỹ về binary heap, đây là tài liệu quý giúp ích rất nhiều cho các học
sinh chuyên Tin của Việt Nam ta. Qua nghiên cứu, tìm hiểu các tài liệu chúng

tôi nhận thấy còn một số loại heap nữa chưa có tài liệu nào trong nước đề cập
đến một cách hoàn chỉnh. Vì vậy trong đề tài này chúng tôi sẽ trình bày về
Fibonacci heap nhằm cung cấp thêm một sự lựa chọn cho các em học sinh
chuyên Tin trong khi lập trình. Chắc chắn đề tài không tránh khỏi những thiếu
sót nhất định, rất mong nhận được những ý kiến đóng góp quý báu của các
thầy cô, các em học sinh và các bạn độc giả.
• Ý nghĩa khoa học của đề tài:
Fibonacci heap có thể được ứng dụng để giải quyết các bài toán cả trong
nghiên cứu lý thuyết và trong thực tiễn. Hiện tại cấu trúc dữ liệu này chưa phổ
biến ở Việt Nam, vì thế đề tài này có thể sẽ là một tài liệu có ích cho các em
học sinh và những người quan tâm có thêm một công cụ mạnh để giải quyết
một số bài toán có liên quan trong lập trình.
• Đề tài gồm có hai chương:
- Chương 1 trình bày về Fibonacci heap
- Chương 2 là phần ứng dụng Fibonacci heap vào việc cải tiến thuật
toán Dijkstra giải bài toán tìm đường đi ngắn nhất trên đồ thị.


2

CHƯƠNG 1
FIBONACCI HEAP
1.1. Tổng quan về cấu trúc dữ liệu heap
Ta có thể dùng mảng hoặc danh sách móc nối để biểu diễn một hàng
đợi ưu tiên, khi đó các thao tác Insert và Update có thể thực hiện với độ phức
tạp là O(1), tuy nhiên các thao tác Find min (Find max) và Extract lại có độ
phức tạp là O(n). Vì vậy, trong thực tế người ta hay dùng cấu trúc dữ liệu trừu
tượng heap (đống) để biểu diễn hàng đợi ưu tiên.
Heap là một cấu trúc dữ liệu trừu tượng, bao gồm một tập n phần tử,
mỗi phần tử có một giá trị khóa xác định. Các phép toán trên một heap được

mô tả trong bảng dưới đây :
Make_ heap

Trả về một heap mới rỗng.

Insert (x,h)

Chèn một giá phần tử x mới,có khóa xác định vào heap

Find_ min

Trả về phần tử có khóa nhỏ nhất, không làm thay đổi heap

Extract_ min

Trả về phần tử có khóa nhỏ nhất và xóa nó ra khỏi heap

Trong một số bài toán còn có thêm các phép toán sau :
Union(h1,h2)

Hợp nhất hai heap h1, h2 thành heap mới, đồng thời xóa h1,
h2

Decrease(∆,x,h) Giảm khóa của phần tử x một lượng ∆ trong heap
Delete(xh)

Xóa phần tử X ra khỏi heap

Heap còn có thể gọi là hàng đợi có độ ưu tiên (priority queue) hay các
đống khả trộn (mergeable heaps).

Một số loại heaps, và thời gian thao tác các phép toán được trình bày
trong bảng dưới đây [2]:
Heaps
Thao tác

Linked Binary

Bionimal

Fibonacci Relax


3

list
make heap

O(1)

O(1)

O(1)

O(1)

O(1)

Insert (x,h)

O(1)


O(logN)

O(logN)

O(1)

O(1)

Find min

O(N)

O(1)

O(logN)

O(1)

O(1)

extract min

O(N)

O(logN)

O(logN)

O(logN)


O(logN)

Union(h1,h2)

O(1)

O(N)

O(logN)

O(1)

O(1)

O(1)

O(logN)

O(logN)

O(1)

O(1)

O(N)

O(logN)

O(logN)


O(logN)

O(logN)

Decrease(∆,x,h
)
Delete(x,h)

Trong phần tiếp theo chúng ta sẽ nghiên cứu kỹ về Fibonacci heap.

1.2. Fibonacci heap
1.2.1. Giới thiệu Fibonacci heap (Đống Fibonacci)
Cấu trúc dữ liệu Fibonacci heap (Đống Fibonacci) được hai giáo sư
Fredman và Tarjan đưa ra vào năm 1986, nhằm áp dụng vào các bài toán tối
ưu trên đồ thị, độ phức tạp của các thuật toán giải một số bài toán điển hình
khi sử dụng Fibonacci heap được thống kê dưới đây [2]:
O(nlogn + m): Cho bài toán tìm đường đi tối ưu xuất phát từ một đỉnh.
O(n2logn + nm): Cho bài toán tìm đường đi tối ưu giữa mọi cặp đỉnh.
O(n2logn + nm): Cho bài toán so khớp hai nhánh có trọng số .
Trước khi định nghĩa Fibonacci heap, ta đưa ra một số khái niệm:
Cây có gốc: Là một cây tự do mà ở đó có một trong các đỉnh được phân
biệt với các đỉnh còn lại và được gọi là gốc.
Cây có thứ tự: Là cây có gốc, mà các nút con trực thuộc một nút cha
được sắp xếp theo một thứ tự xác định.


4

Cây sắp xếp theo đống: Là cây có gốc, và nếu nút x là nút bất kỳ thì nó

có giá trị khóa lớn hơn hoặc bằng (nhỏ hơn hoặc bằng) khóa của cha nó. Từ
đó nút gốc là nút có khóa nhỏ nhất (lớn nhất).
Định nghĩa : Fibonacci heap là một tập hợp các cây được sắp xếp theo
đống. Các cây trong Fibonacci heap không bị ràng buộc về thứ tự[2].

Hình1.1: Fibonacci heap gồm 5 cây sắp xếp theo đống với 14 nút

1.2.2. Cấu trúc Fibonacci heap
Hình 1.2 mô tả cách biểu diễn cấu trúc heap. Mỗi nút x chứa một biến
trỏ p[x] trỏ đến cha của nó và một biến trỏ child[x] trỏ đến một con bất kỳ của
nó. Các con của x được nối kết theo một danh sách nối kết đôi theo vòng tròn
mà ta gọi là danh sách con của x. Mỗi nút y trong danh sách con có các biến
trỏ left[y] và right[y] trỏ đến anh em ruột trái và phải của nó. Nếu nút y là duy
nhất thì left[y] = right[y] = y. Thứ tự xuất hiện các nút trong danh sách con là
tùy ý.
Việc thể hiện danh sách con bằng danh sách nối đôi vòng tròn có 2 ưu
điểm: Thứ nhất, có thể gỡ bỏ một nút ra khỏi danh sách với độ phức tạp là
O(1). Thứ hai, có thể ghép nối 2 danh sách với độ phức tạp tính toán là O(1).
Ngoài ra mỗi nút x còn có :
degree[x]: Lưu số nút trong danh sách con của x.


5

bool mark[x]: Kiểm tra x đã mất một con hay chưa kể từ lần cuối cùng
x trở thành con của một nút khác.
Các gốc của tất cả các cây trong Fibonacci heap được nối kết với nhau
bằng các biến trỏ left, right của chúng tạo thành một danh sách nối kết đôi
vòng tròn gọi là danh sách gốc. Biến trỏ min[H] trỏ đến nút có khóa nhỏ nhất
trong danh sách gốc, từ đây ta sẽ coi min[H] là đại diện của H nói cách khác

là minH quản lý H. Số lượng các nút trong H sẽ được lưu trong biến nH.

Hình 1.2: Mô phỏng cấu trúc Fibonacci heap
Cấu trúc dữ liệu miêu tả một nút trong Fibonacci heap[1]:
node = record
key : integer;
degree : integer;
parent : ^node;
child : ^node;
left : ^node;
right : ^node ;
mark : boolean;
end;

Hàm tiềm năng
Để phân tích đánh giá độ phức tạp trong các phép toán đối với
Fibonacci heap ta sử dụng phương pháp phân tích tiềm năng, khi đó hao phí
khấu trừ của một thuật toán được xem là độ phức tạp của thuật toán đó [1].
Đối với Fibonacci heap, ta sử dụng hàm tiềm năng Φ(H) = t(H) + 2m(H),


6

trong đó: t(H) là số lượng nút trong danh sách gốc, m(H) là số lượng các nút
đánh dấu. Ta mặc nhận rằng ở trạng thái ban đầu Φ(H) = 0.
Ở ví dụ trên : Φ(H) = 5 + 2 × 3 = 11.

1.2.3. Các thao tác trên Fibonacci heap
Ý tưởng chính trong các thao tác trên Fibonacci heap đó là trì hoãn các
công việc chưa cần thiết nếu có thể, chờ đến lúc buộc phải thực hiện thì thực

hiện cùng một lúc nhiều công việc, điều đó giúp giảm bớt các phép tính toán.
Nếu số lượng các cây trong một Fibonacci heap không lớn, ta có thể nhanh
chóng xác định nút cực tiểu mới bằng thủ tục EXTRACT_ MIN. Ta sẽ không
gắng thống nhất các cây trong Fibonacci heap khi chèn một nút mới hoặc hợp
nhất hai đống. Việc thống nhất các cây trong đống chỉ phải làm khi gặp thủ
tục EXTRACT_MIN, là thủ tục tìm nút cực tiểu và xóa nó khỏi đống.
(1) Tạo một Fibonacci heap mới
Để tạo một Fibonacci heap rỗng ta dùng thủ tục FIB_HEAP_ MAKE,
thủ tục này phân bổ và trả về đối tượng Fibonacci heap, trong đó n[H] = 0,
min[H] = NIL, ngay sau lời gọi thủ tục này thì chưa có cây nào trong H.
Vì thế t(H) = 0, m(H) = 0, nên Φ(H) = 0. Như vậy, mức hao phí khấu
trừ (độ phức tạp tính toán) của FIB_HEAP_MAKE bằng với mức hao phí thực
tế O(1) của nó.
(2) Chèn một nút mới
Thủ tục dưới đây chèn nút x với khóa là key[x] vào Fibonacci heap H
được quản lý bởi biến con trỏ min[H]:


7

Procedure FIB_HEAP_INSERT (var x, min[H] : tro); [1]
// tro là một kiểu con trỏ, trỏ vào các node: tro = ^node;
begin
1. degree[x] := 0;
2. p[x] := NIL;
3. child[x] := NIL;
4. left[x] := x;
5. right[x] := x;
6. mark[x] := false;
7. ghép nối danh sách gốc chứa x với danh sách gốc H;

8. if min[H] = NIL hoặc x^.key < minH^.key
9. then minH := x;
10. n[H] = n[H]+1;
end;

Các lệnh từ dòng 1- 6, khởi tạo cấu trúc của nút x, khiến nó trở thành
danh sách nối đôi theo vòng tròn, dòng 7 bổ sung nút x vào danh sách gốc của
H. Như vậy nút x trở thành một cây nút đơn được sắp xếp theo đống trong
Fibonacci heap. Nó không có cây con và không được đánh dấu. Các dòng 8 9 cập nhật min[H]. Dòng 10 tăng số lượng nút trong H.
Có thể nhận ra rằng FIB_HEAP_INSERT(c,min[H]) sẽ không gắng
thống nhất các cây trong đống. Nếu k phép toán FIB_HEAP_INSERT thực
hiện thì sẽ có k cây mới được bổ sung vào danh sách gốc.

Hình 1.3: Minh họa chèn thêm nút có key 21 vào Fibonacci heap


8

Để xác định mức hao phí khấu trừ của FIB_HEAP_INSERT, gọi H là
Fibonacci heap ban đầu và H’ là Fibonacci heap kết quả, thì t(H’) = t(H)+1,
m(H’) = m(H), sự gia tăng trong hàm tiềm năng là : Φ(H’) - Φ(H) = 1 Bởi
mức hao phí thực tế là O(1), nên mức hao phí khấu trừ là O(1) + 1 = O(1).
Mã nguồn thao tác FIB_HEAP_INSERT:
procedure FIB_HEAP_INSERT(var x, minH: tro); [1]
begin
degree[x] := 0;
p[x] := NIL;
child[x] := NIL;
left[x] := x;
right[x] := x;

mark[x] := false;
if minH <> nil // bắt đầu ghép nối danh sách gốc chứa x với danh sách gốc H;
then

begin
x^.left := minH.left;
minH^.left^.right := x;
x^.right := minH;
minH^.left := x;
if minH^.key > x^.key
then minH := x;
end

else minH := x; // kết thúc ghép nối danh sách gốc chứa x với danh sách gốc H;
n[H] = n[H]+1;
end;

Ở đây nút mới x đã được chèn vào bên trái minH, thực tế trong lập trình
ta có thể chèn x vào bên phải minH thì kết quả vẫn giống nhau.
(3) Tìm nút cực tiểu
Nút cực tiểu của Fibonacci heap được trỏ bởi min[H], do đó ta có thể
tìm nút cực tiểu với độ phức tạp tính toán thực tế (hao phí thực tế) là O(1). Do


9

tiềm năng của H không thay đổi, nên mức hao phí khấu trừ của phép toán này
bằng với mức hao phí thực tế của nó là O(1).
(4) Hợp nhất hai Fibonacci heap [2]
Thủ tục dưới đây hợp nhất 2 Fibonacci heap H1 và H2 thành H, đồng

thời hủy H1, H2.
procedure FIB_HEAP_UNION(var min[H1], min[H2], minH : tro);
begin
1. n[H] := 0;
2. min[H] := min[H1];
3. ghép nối danh sách gốc của H2 với danh sách gốc của H;
4. if (min[H1] = NIL) hoặc (min[H2]^.key < min[H1]^.key) then
5. min[H] := min[H2];
6. n[H] := n[H1] + n[H2];
7. giải phóng các đối tượng H1 và H2;
end;

Các dòng 1-3 ghép nối các danh sách gốc của H1 và H2 thành một danh
sách gốc mới H. Các dòng 2, 4, 5 ấn định nút cực tiểu của H, dòng 6 cập nhật
lại số nút của H. Ta có thể thấy trong thủ tục FIB-HEAP-UNION(H1, H2)
không cần thực hiện thống nhất cây.
Sự thay đổi tiềm năng : Φ(H) – (Φ(H1) + Φ(H2)) = 0. Do đó mức hao
phí khấu trừ của FIB_HEAP_UNION bằng với mức hao phí thực tế O(1).
(5) Trích nút cực tiểu[1]
Đây là thủ tục phức tạp nhất của Fibonacci heap. Thủ tục này thực hiện
xóa nút cực tiểu ra khỏi H, đồng thời thực hiện việc thống nhất các cây đã bị
trì hoãn ở các phép toán khác.


10

Đoạn mã giả dưới đây thực hiện trích nút cực tiểu, có sử dụng thủ tục
CONSOLIDATE(H) để thống nhất cây.
procedure FIBO_HEAP_EXTRACT_MIN;
// input: Đống được đại diện bởi biến toàn cục min[H].

// output: Nút có key nhỏ nhất.
begin
1. z := min[H] ;
2. if z <> NIL then
3. for x thuộc con của z do
4.
begin cộng x vào danh sách gốc của H
5.
x.parent := NIL;
6.
end;
7. Gỡ bỏ z ra khỏi danh sách gốc của H;
8. if z = z^.right
9. then min[H] := NIL
10. else min[H] := z^.right;
11. Consolidate(H);
12. n[H] := n[H]-1
end;

FIB_HEAP_EXTRACT_MIN làm việc bằng cách: Trước tiên biến các
nút con của nút cực tiểu thành các gốc, gỡ bỏ nút cực tiểu ra khỏi danh sách
gốc. Sau đó thống nhất danh sách gốc bằng cách kết nối các gốc có số con
bằng nhau cho đến khi số con của các nút trong danh sách gốc là khác nhau.
Dòng 1 dùng biến trỏ z, cho z trỏ vào nút cực tiểu, biến trỏ này được trả
lại ở cuối. Nếu z=NIL, thì Fibonacci heap đã rỗng và ta đã hoàn tất công việc.
Ngược lại, ta xóa nút z ra khỏi H bằng cách khiến tất các con của z thành các
gốc của H, trong các dòng 4 - 9. Nếu z= right[z] hay danh sách chỉ có một nút
duy nhất, thì ta chỉ việc biến H thành rỗng, ngược lại, tạm thời cho biến trỏ
gốc min[H] vào một nút bất kì trong danh sách gốc, ở đây là right[z], sau đó
rút gọn các cây trong Fibonacci heap gọi là thống nhất Fibonacci heap. Điều

này được thực hiện bằng thủ tục CONSOLIDATE.
Nguyên tắc làm việc của thủ tục CONSOLIDATE:
(1) Tìm hai gốc x, y có cùng số nút con trong danh sách con, và key[x]
≤ key[y].


11

(2) Gỡ bỏ y ra khỏi danh sách gốc, cho y làm con của x. Việc này sẽ
được thực hiện bởi thủ tục FIB_HEAP_LINK.
Thủ tục CONSOLIDATE sử dụng thêm một mảng phụ A[0..D(H)], với
D(H) = log2N [1], với ý nghĩa A[i] = y thì y là một gốc có degree[y]=I
(MIHAEL L. FREDMAN, ROBERT ENDRE TARJAN đã chứng minh được là
degree[y] <= D(H)).
procedure COSONLIDATE(var minH : tro);
begin
1. For i = 0 to D(H) do A[i] := NIL;
2. For mỗi nút w trong danh sách gốc của H do
3. Begin
4.
x := w;
5.
d := x^.degree;
6.
While A[d] <> NIL do
7.
Begin
8.
Y:= A[d];
9.

if x^.key > y^. key then tráo đổi x ↔ y;
10.
FIB_HEAP_LINK(H,y,x);
11.
A[d] := NIL;
12.
d := d+1;
13.
End;
14.
A[d] :=x;
15. End;
16. Min[H] := NIL;
17. For i := 0 to D(H) do
18.
If (A[i] <> NIL) then
19.
Begin
20.
Cộng A[i] vào danh sách gốc của H;
21.
If (min[H]=NIL) hoặc ([A[i]]^.key < min[H]^.key)
22.
then Min[H] := A[i];
23.
end;
end;
procedure FIBO_HEAP_LINK(var minH,y,x : tro); [1]
begin
1. Xóa nút y ra khỏi danh sách ban đầu của nó;

2. y^.parent := x;
3. Nối y vào danh sách con của x;
4. x^.degree := x^.degree + 1;
end;


12

Dòng đầu tiên khởi tạo mảng A[i] = NIL, tức là chưa có cây nào có số
con bằng i. Xét một cây con có gốc w trong danh sách gốc, gọi d là số con của
w. Nếu A[d]=NIL thì ta gán A[d]= w. Ngược lại, dòng 6-13: ta chọn cây có
gốc nhỏ hơn trong hai cây w và A[d] làm gốc, và ghép cây còn lại vào danh
sách con của cây kia, kết quả trả về cây trỏ bởi x. Cây x sẽ là cây có số con là
d + 1, tiếp tục xét với cây trỏ bởi A[d+1] và x, nếu A[d+1]=NIL thì dừng lại.
Kết thúc quá trình này ta sẽ được một danh sách gốc mới, trong đó mỗi
gốc có số lượng nút con là khác nhau. Công việc còn lại chỉ là thực hiện cập
nhật nút minH được thực hiện trong các dòng từ 16 – 23.
Hình 1.4 dưới đây mô tả hoạt động của FIB_HEAP_EXTRACT_MIN,
quá trình biến đổi của Fibonacci heap được giải thích như sau:
(a) Một Fibonacci heap.
(b) Trạng thái Fibonacci heap khi gỡ bỏ nút cực tiểu z ra khỏi danh
sách
gốc và bổ sung con của nó vào danh sách gốc.
(c) - (e) Mảng A và các cây trong 3 lần lặp đầu tiên của vòng lặp for
trong thủ tục CONSOLIDATE. Danh sách gốc ban đầu tại nút cực tiểu tạm
thời (sau khi bỏ nút cực tiểu mới), tiếp theo tại biến trỏ right.
(f) - (h) Tình huống đầu tiên khi đi qua vòng lặp while, nút cây có gốc
23 được nối vào cây gốc 7 tạo cây mới có degree =1, do đã tồn tại cây có
degree =1 (a[1]) nên tiếp tục ghép cây trỏ bởi a[1] có gốc là 17 vào cây gốc
7. Tương tự đến bước (h) cây có gốc 24 tiếp tục được nối vào cây gốc 7 tạo

cây có degree = 3, và được A[3] trỏ đến.
(i) - (l) Tình huống trong 4 lần lặp tiếp theo của vòng lặp for.
(m) Trạng thái Fibonacci heap sau khi kết thúc, với biến trỏ mới min[H].


13


14

Hình 1.4: Mô tả hoạt động của FIB_HEAP_EXTRACT_MIN
Mức hao phí của phép toán trích nút cực tiểu bao gồm: O(D(H)) của
phép toán duyệt các nút con của nút cực tiểu thực hiện bởi vòng for trong thủ


15

tục FIB_HEAP_EXTRACT_MIN, D(H) trong việc khởi tạo mảng A trong
thủ tục CONSOLIDATE, D(H) trong vòng for thực hiện cập nhật lại min[H]
(dòng 17 - 23 của thủ tục CONSOLIDATE), cuối cùng là vòng for dòng 2 - 15.
Để đánh giá mức hao phí của vòng for này ta xét: Kích cỡ của danh sách gốc
vào lúc gọi CONSOLIDATE tối đa là D(H) + t(H)-1, bởi nó bao gồm t(H)
nút trong danh sách gốc ban đầu, trừ cho nút gốc đã trích cộng với các con
của nút đã trích mà tối đa là D(H). Mỗi lần qua vòng lặp while của các dòng 6 12, một gốc sẽ được nối với gốc khác, và như vậy tổng lượng công việc được
thực hiện trong vòng lặp for tối đa tỉ lệ với D(H) + t(H). Vậy tổng hao phí
thực tế là O(D(H) + t(H))[1].
Giá trị hàm tiềm năng trước khi trích nút cực tiểu là t(H) + 2m(H) và
giá trị hàm tiềm năng sau đó tối đa là (D(H) +1) + 2m(H), bởi số lượng nút
trong danh sách gốc sau khi trích nút tối đa là D(H) + 1 và số lượng nút đánh
dấu không thay đổi.

Mức hao phí khấu trừ: O(D(H) + t(H)) + ((D(H) + 1) + 2m(H)) -(t(H)
+ 2m(H)) = O(D(H)) = O(logn).

(6) Giảm một khóa và xóa một nút
Giảm khóa một nút
Mã giả dưới đây thực hiện phép toán giảm một khóa [1]
procedure FIB_HEAP_DECREASE_KEY(var minH, x: tro; k: longint);
begin
1. if k > x^.key then
2. writeln(‘Khóa mới lớn hơn khóa hiện hành’);
3. x^.key := k;
4. y := x^.parent;
5. if (y <> NIL) và (x^.key < y^.key) then
6.
begin
7.
CUT(minH,x,y)
8.
CASCADING_CUT(minH,y);
9.
end;
10. if x^.key < minH^.key then
11.
minH := x;


16

end;
procedure CUT(var minH,x,y : tro);

begin
1. Gỡ bỏ x ra khỏi danh sách con của y, giảm lượng degree[y] một đơn vị;
2. Cộng x và danh sách gốc của H;
3. p[x] := NIL;
4. x^.mark := FALSE;
end;
procedure CASCADING_CUT(var minH, y: tro);
begin
1. z := p[y];
2. if z <> NIL then
3.
if mark[y] = FALSE then
4.
mark[y] := TRUE
5. else
6.
begin CUT(minH, y, z)
7.
CASCADING_CUT(H, z)
8.
end;
end;

Thủ tục FIB_HEAP_DECREASE_KEY làm việc như sau: Các dòng 13 đảm bảo khóa mới không lớn hơn khóa hiện tại, và sau đó gán khóa mới
cho x. Nếu x là một gốc hoặc key[x] ≥ key[y] với y là cha của x thì không cần
thay đổi cấu trúc của Fibonacci heap - các dòng 4 - 5 kiểm tra điều kiện này.
Ngược lại, thứ tự đống bị vi phạm, ta cần phải tổ chức lại. Ta bắt đầu
bằng cách cắt nối kết giữa x và cha y của nó, biến x thành một gốc.
Ta dùng trường mark để được cận thời gian tốt hơn. Xét một nút x đã
từng bị chuyển thành con của nút khác. Ta đánh dấu mark[x] = true khi nó

mất con thứ nhất, khi x mất con thứ 2 ta bỏ đánh dấu nó đưa nó vào danh sách
gốc. Bởi khi gỡ một nút x và ghép vào danh sách gốc, thì có thể tác động đến
trường mark của các nút cha, ông, cụ.. của nó, cho nên ta sử dụng một thao
tác đệ quy cắt liên hoàn CASCADING_CUT để thực hiện kiểm tra đối với
các nút cha, ông…
Sau khi xảy ra xong tất cả tác vụ cắt liên hoàn, các dòng 8, 9 của
FIB_DECREASE_KEY hoàn tất bằng cách cập nhất lại nút minH.


17

Ta sẽ chứng tỏ mức hao phí khấu trừ của FIB_HEAP_DECREASE_KEY
chỉ là O(1).
Thủ tục FIB_HEAP_DECREASE_KEY có độ phức tạp là O(1) (các lệnh từ
1 - 4) cộng với việc thực hiện các tác vụ cắt liên hoàn. Giả sử thủ tục
CASCADING_CUT được gọi đệ qui c lần, mỗi lệnh CASCADING_CUT có độ

phức tạp là O(1). Như vậy mức hao phí thực tế của thủ tục FIB_HEAP_
DECREASE_KEY là O(c).

Tiếp theo ta sẽ tính sự thay đổi tiềm năng cho H là Fibonaci heap ngay
trước phép toán FIB_HEAP_DECREASE_KEY. Mỗi lệnh gọi đệ quy của
CASCADING_CUT, tăng tối đa c cây ở gốc, giảm tối đa c-2 nút đánh dấu, từ
đó suy ra sự thay đổi về tiềm năng là:
((t(H) + c) + 2(m(H) – c + 2)) - (t(H) + 2m(H)) = 4 - c
Như vậy chi phí khấu trừ của FIB_HEAP_DECREASE_KEY là :
O(c) + 4 - c = O(1).
Như vậy, ta có thể hiểu được tại sao hàm tiềm năng lại bao gồm 2 lần
số lượng nút đánh dấu: Khi một nút đánh dấu y được cắt bởi một tác vụ cắt
liên hoàn, nó được xóa đánh dấu, do đó tiềm năng được rút gọn đi 2 gồm: một

thanh toán cho thao tác cắt và xóa đánh dấu, hai là bù cho đơn vị gia tăng
trong tiềm năng do nút y trở thành gốc.


18

Hình 1.5. Mô tả thao tác FIB_HEAP_DECREASE_KEY
(a) Fibonacci heap ban đầu
(b) Nút có khóa 46 giảm xuống 15, trở thành một gốc, cha của nó 24
được đánh dấu.
(c)-(e) Nút có khóa 35 giảm xuống thành 5, các nút cha 26, 24 được cắt
liên hoàn. Cuối cùng cập nhật lại nút minH.
Xóa một nút
Ta có thể dễ dàng xóa một nút ra khỏi Fibonacci heap với độ phức tạp
là O(logn), như trong mã giả dưới đây. Mặc nhận rằng không có giá trị khóa
nào là -∞ trong Fibonacci heap.


19

procedure FIB_HEAP_DELETE(var minH, x : tro);
begin
1. FIB_HEAP_DECREASE_KEY(minH, x, - ∞);
2. FIB_HEAP_EXTRACT_MIN(minH);
end;

FIB_HEAP_DELETE(H, x) biến nút x thành nút cực tiểu bằng cách
gán cho nó khóa - ∞ thông qua thủ tục FIB_HEAP_DECREASE_KEY, sau đó
loại nó ra khỏi Fibonacci heap bằng thủ tục FIB_HEAP_EXTRACT_MIN.
Chi phí khấu trừ của FIB_HEAP_DELETE là tổng chi phí khấu trừ O(1)

của FIB_HEAP_DECREASE_KEY và O(logn) của FIB_HEAP_EXTRACT_MIN.

1.3. Kết luận chương
Ở chương 1 này chúng ta đã nghiên cứu về Fibonacci heap, chúng ta có
thể ứng dụng cấu trúc dữ liệu trừu tượng này để cải tiến Thuật toán Dijkstra
tìm đường đi ngắn nhất, và một số bài toán khác như bài toán sắp xếp, bài
toán tìm cây khung cực tiểu, bài toán so khớp hai nhánh có trọng số…
Tuy có ưu thế về tốc độ (độ phức tạp tính toán) đối với hầu hết các thao
tác với heap nhưng Fibonacci heap vẫn chưa được nhiều người lập trình sử
dụng, lý do là vì để cài đặt Fibonacci heap chúng ta phải dùng danh sách móc
nối và nói chung là việc cài đặt phức tạp hơn. Tuy nhiên trong trường hợp
không bị giới hạn về thời gian lập trình và cần xử lý những đồ thị thưa, ta có
thể dùng Fibonacci heap để tăng thêm hiệu quả của thuật toán.
Chương 2 của đề tài sẽ ứng dụng Fibonacci heap vào việc cải tiến thuật
toán Dijkstra giải bài toán tìm đường đi ngắn nhất trên đồ thị.


20

CHƯƠNG 2
ỨNG DỤNG FIBONACCI HEAP CẢI TIẾN THUẬT TOÁN
DIJKSTRA

2.1. Sơ đồ thuật toán Dijkstra kết hợp với Fibonacci Heap
Sơ đồ thuật toán Dijkstra nguyên thủy với độ phức tạp O(n2) như sau:
procedure dijkstra;
// input: Đồ thị G, các biến toàn cục s, t;
// ouput: Khoảng cách từ s đến t;
begin
Repeat

u := FindMin();
if u = t then exit;
Đánh dấu u đã cố định;
Repair(u); // tiến hành sửa nhãn cho các đỉnh kề u
Until False;
end;

Bây giờ chúng ta sẽ tổ chức mảng nhãn d theo cấu trúc Fibonacci heap,
khi đó mô hình thuật toán Dijkstra có thể viết lại như sau:
procedure dijkstra_fibo_heap;
// input: Đồ thị G, đống H. S, t là các biến toàn cục.
// output: Khoảng cách từ s đến t.
begin
Repeat
P := FIB_HEAP_EXTRACT_MIN(H);
u := p^. u; // u là một trường mới của các nút trong Fibonacci heap để lưu nhãn
//của đinh (tên đỉnh) mà nút đại diện.
if u = t then exit;
Đánh dấu u đã cố định ;
for (v thuộc ke(u)) do
if (d[v] > d[u] + c[u,v] ) then
begin


21

d[v] := d[u] + c[u,v];
FIB_HEAP_DECREASE_KEY(H, ptr[v], d[v]) ;// ptr[v] là nút trong
//H có nhãn là v.
end;

Until false;
end;

Vòng lặp Repeat thực hiện lặp tối đa là n lần, thao tác FIB_HEAP_
EXTRACT_MIN(H) trích nút cực tiểu có độ phức tạp là O(logn), vì thế tính

trong toàn bộ vòng repeat

thì tổng số thao tác này có độ phức tạp là

O(nlogn).
Thao tác FIB_HEAP_DECREASE_KEY(H, ptr[ v], d[v]) có độ phức
tạp là O(1), số lần lặp trong một vòng for chỉ bằng số lượng đỉnh kề u, vì vậy
nếu chúng ta sử dụng danh sách liên kết để tổ chức các cạnh thì độ phức tạp
của tất cả các vòng lặp for trong vòng lặp repeat sẽ là O(m).
Từ hai nhận xét trên suy ra thuật toán Dijkstra Fibonacci heap có độ
phức tạp là cỡ O(nlogn +m), với m là số cạnh của đồ thị. Với những đồ thị
thưa thì đây sẽ là một thuật toán rất tốt.

2.2. Ứng dụng Dijkstra Fibonacci heap giải bài toán tìm đường
đi ngắn nhất
2.2.1 Một số kiểu dữ liệu và các biến trong chương trình
Chương trình sử dụng một kiểu con trỏ được khai báo dạng sau:
type tro = ^node;
node = record
sohieu, degree: longint;
key: int64;
parent, child, left, right: tro;
mark : boolean;
end;


Trường sohieu của một node là tên của đỉnh mà node đó đại diện, các
trường khác trong node hiểu như đã trình bày ở chương 1.


22

Chương trình sử dụng biến mảng d dạng d: array[1..nmax] of tro;
Mảng này thực chất là chứa n biến trỏ, mỗi biến trỏ trỏ vào một node
của Fibonacci heap, d[i] trỏ vào node đại diện cho đỉnh i của đồ thị, trường
key của node này là nhãn khoảng cách từ đỉnh s đến đỉnh i. Việc dùng mảng d
này cho phép chương trình có thể truy nhập vào các nút trong Fibonacci heap
khi biết sohieu của node này.
Các biến mảng adj[i], head[j] dùng để lưu đồ thị ở dạng danh sách kề
kiểu móc nối.

2.2.2. Một số hàm và thủ tục trong chương trình
Thủ tục Enter: Thủ tục này có nhiệm vụ đọc dữ liệu từ tệp input có
dạng: Dòng đầu là 4 số nguyên N, M, S, T, trong đó N là số đỉnh, M là số
cung của đồ thị, S, T là hai đỉnh của đồ thị mà ta cần phải tìm khoảng cách từ
S đến T. M dòng sau, mỗi dòng gồm 3 số nguyên dương u, v, l với ý nghĩa có
cung (u, v) cố độ dài là l.
Sau khi thực hiện thủ tục này số đỉnh của đồ thị được lưu trong biến n,
số cung lưu trong biến m. Đồ thị được lưu trữ dưới dạng danh sách kề như
sau:
Với mỗi đỉnh i thì các đỉnh kề với i được xác định thông qua head[i],
nếu h[i] = k ≠ 0 thì adj[k]. v là đỉnh kề thứ nhất của i. Địa chỉ của đỉnh kề tiếp
theo của i là adj[k].link: Nếu adj[k].link = k1 ≠ 0 thì đỉnh kề thứ 2 của i là
adj[k1].v. Quá trình tìm đỉnh kề với i kết thúc khi địa chỉ tìm được bằng 0.
Như vậy nếu ngay từ đầu head[i] = 0 thì danh sách kề của i bằng rỗng, nghĩa

là từ i không có cung nối tới bất kỳ đỉnh nào cả.
Thủ tục INSERT(var x, minH:tro): Thủ tục này chèn một nút mới được
trỏ bởi con trỏ x vào Fibonacci heap được trỏ bởi minH. Trong thủ tục này x


23

và minH đều là các tham số hình thức (khi gọi thủ tục thì tham số hình thức
phải thay bằng các biến tương ứng).
Thủ tục FIB_HEAP_LINK(var y, x:tro): Biến gốc y (được trỏ bởi con
trỏ y) làm con của gốc x (y và x đều là các tham số hình thức).
Thủ tục CUT(var minH, x, y : tro): Đưa nút x ra khỏi danh sách con
của nút y, biến x thành một gốc. MinH, x, y đều là các tham số hình thức.
Thủ tục CASCADING_CUT(var minH, y : tro): Thủ tục cắt liên hoàn
như đã trình bày ở chương 1.
Thủ tục FIB_HEAP_DECREASE_KEY(var minH, x: tro; k: longint):
Thủ tục này sẽ thay x^.key bằng một giá trị mới nhỏ hơn là k, nếu k nhỏ hơn
khóa của nút y là cha của x thì sẽ cắt nhánh cây gốc x bằng thủ tục CUT(x, y).
Thủ tục Consolidate(var minH : tro): Thủ tục này sẽ thống nhất danh
sách gốc, nghĩa là sẽ ghép hai gốc có cùng số con thành một gốc, việc này sẽ
được lặp cho đến khi không tồn tại hai gốc có số nút con bằng nhau. Trong
thủ tục này chúng tôi đã chọn D(H) = log 2N +1 thay vì D(H) = log2N, lý do là
nếu chọn D(H) = log2N thì việc thống nhất các gốc trong heap của thủ tục này
trong một số trường hợp sẽ bỏ sót mất một gốc (phải chăng việc chứng minh
degree[y] <= D(H) = log2N còn cần phải kiểm chứng lại ?)
Thủ tục FIB_HEAP_EXTRACT_MIN(var z : tro): Thủ tục này thực
hiện xóa nút cực tiểu ra khỏi H, đồng thời thực hiện việc thống nhất các gốc
đã bị trì hoãn ở các phép toán khác. Đoạn mã nguồn sau mô tả thủ tục
FIB_HEAP_EXTRACT_MIN
procedure FIB_HEAP_EXTRACT_MIN(var z : tro);

// input: Fibonacci heap H.
//output: Nút có khóa cực tiểu của H.
var x, tam, tt, tam2 : tro;
i: longint;
begin
z := minH;