CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

(ALGORITHMS AND DATA STRUCTURES)

 

1. Khái niệm

Cấu trúc dữ liệu (Data Structure)

là cách lập trình để lưu trữ dữ liệu để dữ liệu có thể được sử dụng một cách hiệu quả. Hầu hết mọi ứng dụng doanh nghiệp đều sử dụng nhiều kiểu cấu trúc dữ liệu khác nhau theo cách này hay cách khác, vì nó mang lại nhiều lợi ích rất lớn không chỉ cho việc lưu trữ dữ liệu. Series tự học CTDL & GT này sẽ cung cấp cho bạn sự hiểu biết chi tiết và chuyên sâu về Cấu trúc dữ liệu cần thiết từ cơ bản tới nâng cao và áp dụng nó vào thuật toán.

Thuật toán(Algorithms)

là một thủ tục từng bước, xác định một tập hợp các lệnh được thực hiện theo một thứ tự nhất định để có được đầu ra mong muốn. Các thuật toán thường được tạo độc lập với các ngôn ngữ cơ bản, tức là một thuật toán có thể được triển khai bằng nhiều ngôn ngữ lập trình(C/C++, Java, Python, PHP…), với series tự học này sẽ cung cấp cho các bạn các ví dụ, code mẫu trên nhiều ngôn ngữ khác nhau…

Cấu trúc dữ liệu và giải thuật(CTDL & GT)

là sự kết hợp và áp dụng một hoặc nhiều cấu trúc dữ liệu nào đó vào một hoặc nhiều thuật toán nào đó để có được đầu ra mong muốn một cách tối ưu và tốt nhất khi dữ liệu có số lượng cực lớn.

2. Tại sao phải học cấu trúc dữ liệu và giải thuật?

Khi các ứng dụng ngày càng phức tạp và nhiều dữ liệu, có ba vấn đề phổ biến mà các ứng dụng phải đối mặt ngay bây giờ.

Tìm kiếm dữ liệu – Tìm kiếm một sản phẩm nào đó trong cả tỉ tỉ dữ liệu càng ngày càng lớn. Khi dữ liệu phát triển, tìm kiếm sẽ trở nên chậm hơn. Vì vậy cần CTDL & GT để nâng cao hiệu suất hơn.
Tốc độ bộ xử lý – Tốc độ bộ xử lý mặc dù rất cao nhưng sẽ bị giới hạn nếu dữ liệu tăng lên đến hàng tỷ dữ liệu.
Nhiều yêu cầu – Vì hàng nghìn người dùng có thể tìm kiếm dữ liệu đồng thời trên một máy chủ web, ngay cả máy chủ nhanh cũng bị lỗi trong khi tìm kiếm dữ liệu.
Để giải quyết các vấn đề nêu trên, cấu trúc dữ liệu ra đời để giải cứu. Dữ liệu có thể được tổ chức theo cấu trúc dữ liệu theo cách mà tất cả các mục có thể không được yêu cầu tìm kiếm và dữ liệu cần thiết có thể được tìm kiếm gần như ngay lập tức.

3. Ứng dụng của nó

Tìm kiếm – Thuật toán tìm kiếm một mục trong cấu trúc dữ liệu.
Sắp xếp – Thuật toán sắp xếp các mục theo một thứ tự nhất định.
Chèn – Thuật toán chèn mục trong cấu trúc dữ liệu.
Cập nhật – Thuật toán cập nhật một mục hiện có trong cấu trúc dữ liệu.
Xóa – Thuật toán xóa một mục hiện có khỏi cấu trúc dữ liệu.
Các vấn đề sau có thể được giải quyết bằng cách sử dụng Cấu trúc dữ liệu:

Chuỗi số Fibonacci
Vấn đề Knapsack
Tháp Hà Nội
Tất cả các cặp đường đi ngắn nhất của Floyd-Warshall
Con đường ngắn nhất của Dijkstra
Lập kế hoạch dự án

CHƯƠNG 1: GIỚI THIỆU VÀ ĐÁNH GIÁ GIẢI THUẬT

Tải về

CHƯƠNG 2: GIẢI THUẬT TÌM KIẾM

Tải về

CHƯƠNG 3: GIẢI THUẬT SẮP XẾP

Tải về

CHƯƠNG 4: GIẢI THUẬT SẮP XẾP NÂNG CAO

Tải về

CHƯƠNG 5: LÝ THUYẾT ĐỒ THỊ

Tải về

CHƯƠNG 6: ARRAY LIST

Tải về

CHƯƠNG 7: DANH SÁCH LIÊN KẾT

Tải về

CHƯƠNG 8: NGĂN XẾP -HÀNG ĐỢI (STACK – QUEUE)

Tải về

CHƯƠNG 9: HASH TABLE

Tải về

CHƯƠNG 10: TREE BINARY SEARCH TREE

Tải về

CHƯƠNG 1: GIẢI THUẬT TÌM KIẾM

Tải về

CHƯƠNG 2: GIẢI THUẬT SẮP XẾP

Tải về

CHƯƠNG 3: LÝ THUYẾT ĐỒ THỊ

Tải về

CHƯƠNG 4: ARRAY LIST – LINKED LIST

Tải về

CHƯƠNG 5: STACK – QUEUE

Tải về

CHƯƠNG 6: HASH TABLE (BẢNG BĂM)

Tải về

CHƯƠNG 7: CÂY NHỊ PHÂN

Tải về Tải đề 1 Tải đề 2 Tải đề 3 Tải đề 4

Đề ôn tập thi kết thúc môn tháng 11 năm 2022

Tải về

 

Ôn tập kết thúc môn – CTDL & Giải thuật năm 2023
Câu 1. Áp dụng giải thuật tìm kiếm nhị phân – Binary Search.

Mảng sắp xếp tăng dần. Dãy số gồm 8 phần tử x=12 (n=8)

1 2 4 5 6 8 12 15

Ta được:

left     mid       right
1 2 4 5 6 8 12 15
i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7

 

B.1: left =0; right =\mathrm{n}-1=7
B.2: mid =( left + right ) / 2=(0+7) / 2=3 (lấy nguyên)
\mathrm{mid}=3 \rightarrow \mathrm{a}[\mathrm{mid}]=\mathrm{a}[3]=5<\mathrm{x}=12 :
left = mid +1=3+1=4 \quad( right =7)
B.3: nếu left < right (4<7)

 

        left mid   right
1 2 4 5 6 8 12 15
i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7

 

B.2: left =4; right =7
Mid =(4+7) / 2=5 \rightarrow \mathrm{a}[\mathrm{mid}]=\mathrm{a}[5]=8<\mathrm{x}=12 :
left = mid +1=5+1=6( right =7)
B.3: nếu left < right (6<7)

 

 

            left = mid right
1 2 4 5 6 8 12 15
i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7

 

B.2: \mathrm{mid}=( left + right ) / 2=(6+7) / 2=6
\mathrm{a}[\mathrm{mid}]=\mathrm{a}[6]=12=\mathrm{x}.

Kết thúc

Câu 2. Áp dụng giải thuật tìm kiếm nhị phân – Binary Search.
Mảng sắp xếp tăng dần. Dãy số gồm 9 phần tử x=35 (n=9)

4 6 10 15 21 25 30 36 50

Ta được:

 

left       mid       right
4 6 10 15 21 25 30 36 50
i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8

 

B.1: left =0; right =\mathrm{n}-1=8
B.2: mid =( left + right ) / 2=(0+8) / 2=4 
\mathrm{mid}=4 \rightarrow \mathrm{a}[\mathrm{mid}]=\mathrm{a}[4]=21<\mathrm{x}=35 :
left = mid +1=4+1=5 \quad( right =8)
B.3: nếu left < right (5<8)

 

          left mid   right
4 6 10 15 21 25 30 36 50
i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8

B.2: left =5; right =8
Mid =(5+8) / 2=6 \rightarrow \mathrm{a}[\mathrm{mid}]=\mathrm{a}[6]=30<\mathrm{x}=35 :
left = mid +1=6+1=7( right =8)
B.3: nếu left < right (7<8)

 

 

              left = mid right
4 6 10 15 21 25 30 36 50
i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8

B.2: \mathrm{mid}=( left + right ) / 2=(7+8) / 2=7
\mathrm{a}[\mathrm{mid}]=\mathrm{a}[7]=36 > 35.

Kết thúc: Thuật toán không tìm thấy

 

Câu 3. Áp dụng giải thuật sắp xếp nổi bọt – Bubble Sort.
Thực hiện sắp xếp mảng A = [19, 13, 6]

Ta có:
Cho Mảng A = [19,13,6]


B.1: i = 0;
B.2: j = 0;
B.3: nếu A[j] > A[j+1] (A[0] > A[1]; 19 > 13) thì Hoán đổi giữa 19 và 13
[13,19,6];
B.4: nếu j < (n-i-1) (0 < (2-0-1)) : Đúng thì j = j+1= 0+1= 1
và quay lui B.3;


B.3: nếu A[j] > A[j+1] (A[1] > A[2]; 19 > 6) thì Hoán đổi giữa 19 và 6
[13, 6,19];
B.4: nếu j < (n-i-1) (1 < (2-0-1)): Sai thì chuyển sang B.5
B.5: nếu i < (n-1) (0 < 1): Đúng thì i =i+1 = 0 +1 = 1 và quay lại B.2


B.2: j = 0 (i= 1) ;
B.3: nếu A[0] > A[1] (13 > 6) thì Hoán đổi giữa 13 và 6
[6, 13,19] ;
B.4: Nếu (j < n – i – 1) (0 < 0) : Sai thì chuyển sang B.5
B.5: Nếu (i < n – 1) (1 < 1): Sai thì Dừng Kết thúc.
Vậy mảng được sắp xếp là:
[6, 13,19].


Câu 4. Áp dụng giải thuật sắp xếp nổi bọt – Bubble Sort.
Thực hiện sắp xếp mảng A = [40, 15, 75, 30]

Câu 5. Phương pháp chia h(x) = x % M
Tính giá trị băm cho các khóa 1533 ; 3471, 1363, 2564
M = 5 (kích thước bảng)

Giải

 

STT Key Hash Chỉ mục mảng
1 1533 1533 % 5 = 3 3
2 3471 3471 % 5 = 1 1
3 1363 1363 % 5 = 3 3
4 2564 2564 % 5 = 4 4

 

Cho cây nhị phân như sau Sử dụng kỹ thuật dò tuyến tính giải quyết các cặp xung đột, ta được chỉ mục mảng sau:

STT Key Hash Chỉ mục mảng Sau kỹ thuật Linear Probing chỉ mục mảng
1 1533 1533 % 5 = 3 3 3
2 3471 3471 % 5 = 1 1 1
3 1363 1363 % 5 = 3 3 4
4 2564 2564 % 5 = 4 4 5

 

Câu 6. Phương pháp chia h(x) = x % M
Tính giá trị băm cho các khóa 1, 2, 42, 4, 12, 14, 17, 13, 37
M = 20 (kích thước bảng)

Giải

STT Key Hash Chỉ mục mảng
1 1 1 % 20 = 1 1
2 2 2 % 20 = 2 2
3 42 42 % 20 = 2 2
4 4 4 % 20 = 4 4
5 12 12 % 20 = 12 12
6 14 14 % 20 = 14 14
7 17 17 % 20 = 17 17
8 13 13 % 20 = 13 13
9 37 37 % 20 = 17 17

 

Cho cây nhị phân như sau Sử dụng kỹ thuật dò tuyến tính giải quyết các cặp xung đột, ta được chỉ mục mảng sau:

 

STT Key Hash Chỉ mục mảng Sau kỹ thuật Linear Probing chỉ mục mảng
1 1 1 % 20 = 1 1 1
2 2 2 % 20 = 2 2 2
3 42 42 % 20 = 2 2 3
4 4 4 % 20 = 4 4 4
5 12 12 % 20 = 12 12 12
6 14 14 % 20 = 14 14 14
7 17 17 % 20 = 17 17 17
8 13 13 % 20 = 13 13 13
9 37 37 % 20 = 17 17 18

 

Câu 7. Cho cây nhị phân như sau

a) Tìm kiếm node có giá trị x = 22.
b) Lập cây nhị phân gồm mức 0, mức 1, mức 2, mức 3.

Giải:

a)

Thực hiện các bước như sau:
Bước 1: Bắt đầu, từ node gốc có giá trị bằng 30. Do 22 < 30, nên node cẩn tìm phía cây con bên trái;
Bước 2: Node gốc của cây con bên trái bằng 20, do 22 > 20, nên node cẩn tìm phía cây con bên phải;
Bưóc 3: Node tiếp theo bằng 24, do 22 < 24, nên node cẩn tìm phía cây con bên trái;
Buó́c 4: Node này có giá trị bằng x = 22, nên ta thu được node cần tìm trong cây nhị phân.

b)

 

 

 

Câu 8. Cho cây nhị phân như sau

a) Tìm kiếm node có giá trị x = 47.
b) Lập cây nhị phân gồm mức 0, mức 1, mức 2, mức 3.

Giải:

a)

Thực hiện các bước như sau:
Bước 1: Bắt đầu, từ node gốc có giá trị bằng 70. Do 47 < 30, nên node cẩn tìm phía cây con bên trái;
Bước 2: Node gốc của cây con bên trái bằng 65, do 47 < 65, nên node cẩn tìm phía cây con bên trái;
Bưóc 3: Node tiếp theo bằng 40, do 47 > 40, nên node cẩn tìm phía cây con bên phải;
Buó́c 4: Node này có giá trị bằng x = 47 khác 54, nên node có giá trị x = 47 không tìm thấy trong cây nhị phân.

b)

 

 

Câu 9.
a) Viết ma trận kề từ đồ thị có hướng (Hình 1) như sau
b) Áp dụng thuật toán tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong đồ thị có hướng (Hình 1) như sau

 

Giải:

Ma trận kề

  a b c d e z
a 0 1 0 1 0 0
b 0 0 1 1 0 0
c 0 0 0 0 1 1
d 0 0 1 0 1 0
e 0 0 0 0 0 1
z 0 0 0 0 0 0

 

+Thực hiện bước 1:
Đặt: T:=\{a, b, c, d, e, z\}
\mathrm{L}(\mathrm{a}):=0, \mathrm{~L}(\mathrm{~b})=\mathrm{L}(\mathrm{c})=\mathrm{L}(\mathrm{d})=\mathrm{L}(\mathrm{e})=\mathrm{L}(\mathrm{z}):=\infty

P(a) = P(b) = P(c) = P(d) = P(e) = P(z) := \phi

+Thực hiện bước 2:

\mathrm{L}(\mathrm{a})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=0

Suy ra: v=a\mathrm{T}:=\mathrm{T}-\{a\}=\{b, c, d, e, z\}
+ Thực hiện bước 3: z \neq v, sang bước 4.

+Thực hiện bước 4:

Xét đỉnh \mathrm{b} và đỉnh \mathrm{d} kề đỉnh \mathrm{a}. Ta có

\mathrm{L}(\mathrm{b}):=\infty>\mathrm{L}(\mathrm{a})+\mathrm{w}(\mathrm{a}, \mathrm{b})=0+3=3 \Rightarrow \mathrm{L}(\mathrm{b}):=3 \text {, gán } \mathrm{P}(\mathrm{b}):=\mathrm{a}

\mathrm{L}(\mathrm{d}):=\infty>\mathrm{L}(\mathrm{a})+\mathrm{w}(\mathrm{a}, \mathrm{d})=0+4=4 \Rightarrow \mathrm{L}(\mathrm{d}):=4, \text { gán } \mathrm{P}(\mathrm{d}):=\mathrm{a}

 

+Thực hiện bước 2:

\mathrm{L}(\mathrm{b})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=3

Suy ra: v=b\mathrm{T}:=\mathrm{T}-\{\mathrm{b}\}=\{c, d, e, z\}

+ Thực hiện bước 3: z \neq v, sang Bước 4.

+Thực hiện bước 4:

Xét đỉnh \mathrm{d} và đỉnh \mathrm{c} kề đỉnh \mathrm{b}. Ta có
\mathrm{L}(\mathrm{c}):=\infty>\mathrm{L}(\mathrm{b})+\mathrm{w}(\mathrm{b}, \mathrm{c})=3+6=9 \Rightarrow \mathrm{L}(\mathrm{c}):=9, gán \mathrm{P}(\mathrm{c}):=\mathrm{b};
\mathrm{L}(\mathrm{d}) : =4: không đổi

 

+Thực hiện bước 2:

\mathrm{L}(\mathrm{d})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=4

Suy ra:

v=d  và  \mathrm{T}:=\mathrm{T}-\{\mathrm{d}\}=\{c, e, z\}

+ Thực hiện bước 3: z \neq v, sang Bước 4.
+Thực hiện bước 4:

Xét đỉnh \mathrm{e} và đỉnh \mathrm{c} kề đỉnh \mathrm{d}. Ta có

\mathrm{L}(\mathrm{e}):=\infty>\mathrm{L}(\mathrm{d})+\mathrm{w}(\mathrm{d}, \mathrm{e})=4+4=8 \Rightarrow \mathrm{L}(\mathrm{e}):=8, \text { gán } \mathrm{P}(\mathrm{e}):=\mathrm{d}:

\mathrm{L}(\mathrm{c}):=9>\mathrm{L}(\mathrm{d})+\mathrm{w}(\mathrm{d}, \mathrm{c})=4+1=5 \Rightarrow \mathrm{L}(\mathrm{c}):=5, \text { gán } \mathrm{P}(\mathrm{c}):=\mathrm{d}:

+Thực hiện bước 2:

\mathrm{L}(\mathrm{c})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=5

Suy ra: v=c\mathrm{T}:=\mathrm{T}-\{\mathrm{c}\}=\{e, z\}

+ Thụ̣c hiện bước 3: z \neq v, sang bước 4.
+Thực hiện bước 4:
Xét đỉnh e và đỉnh \mathrm{z} kề đỉnh \mathrm{c}. Ta có
\mathrm{L}(\mathrm{e}):=8 : không đổi;
\mathrm{L}(\mathrm{z}):=\infty>\mathrm{L}(\mathrm{c})+\mathrm{w}(\mathrm{c}, \mathrm{z})=5+3=8 \Rightarrow \mathrm{L}(\mathrm{z}):=8, gán \mathrm{P}(\mathrm{z}):=\mathrm{c} ;

+Thực hiện bước 2:
\mathrm{L}(\mathrm{z})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=8
Suy ra: v=z\mathrm{T}:=\mathrm{T}-\{\mathrm{z}\}
+ Thực hiện bước 3: z=v, kết thúc.
\mathrm{L}(\mathrm{z})=8 là độ dài đường đi ngắn nhất từ \mathrm{a} đến \mathrm{z}.
Vậy đường đi ngắn nhất là: \mathrm{a} \rightarrow \mathrm{d} \rightarrow \mathrm{c} \rightarrow \mathrm{z}.

 

 

Câu 10.
a) Viết ma trận kề từ đồ thị có hướng (Hình 2) như sau
b) Áp dụng thuật toán tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong đồ thị có hướng (Hình 2) như sau

 

 

Giải:

Ma trận kề

  a b c d e z
a 0 1 0 1 0 0
b 0 0 1 1 0 0
c 0 0 0 0 1 1
d 0 0 1 0 1 0
e 0 0 0 0 0 1
z 0 0 0 0 0 0

 

+Thực hiện bước 1:
Đặt: T:=\{a, b, c, d, e, z\}
\mathrm{L}(\mathrm{a}):=0, \mathrm{~L}(\mathrm{~b})=\mathrm{L}(\mathrm{c})=\mathrm{L}(\mathrm{d})=\mathrm{L}(\mathrm{e})=\mathrm{L}(\mathrm{z}):=\infty

P(a) = P(b) = P(c) = P(d) = P(e) = P(z) := \phi

+Thực hiện bước 2:

\mathrm{L}(\mathrm{a})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=0

Suy ra: v=a\mathrm{T}:=\mathrm{T}-\{a\}=\{b, c, d, e, z\}
+ Thực hiện bước 3: z \neq v, sang bước 4.

+Thực hiện bước 4:

Xét đỉnh \mathrm{b} và đỉnh \mathrm{d} kề đỉnh \mathrm{a}. Ta có

\mathrm{L}(\mathrm{b}):=\infty>\mathrm{L}(\mathrm{a})+\mathrm{w}(\mathrm{a}, \mathrm{b})=0+2=2 \Rightarrow \mathrm{L}(\mathrm{b}):=2 \text {, gán } \mathrm{P}(\mathrm{b}):=\mathrm{a}

\mathrm{L}(\mathrm{d}):=\infty>\mathrm{L}(\mathrm{a})+\mathrm{w}(\mathrm{a}, \mathrm{d})=0+5=5 \Rightarrow \mathrm{L}(\mathrm{d}):=5, \text { gán } \mathrm{P}(\mathrm{d}):=\mathrm{a}

+Thực hiện bước 2:

\mathrm{L}(\mathrm{b})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=2

Suy ra: v=b\mathrm{T}:=\mathrm{T}-\{\mathrm{b}\}=\{c, d, e, z\}

+ Thực hiện bước 3: z \neq v, sang bước 4.

+Thực hiện bước 4:

Xét đỉnh \mathrm{d} và đỉnh \mathrm{c} kề đỉnh \mathrm{b}. Ta có
\mathrm{L}(\mathrm{c}):=\infty>\mathrm{L}(\mathrm{b})+\mathrm{w}(\mathrm{b}, \mathrm{c})=2+7=9 \Rightarrow \mathrm{L}(\mathrm{c}):=9, gán \mathrm{P}(\mathrm{c}):=\mathrm{b};
\mathrm{L}(\mathrm{d}): =5 > \mathrm{L}(\mathrm{b})+\mathrm{w}(\mathrm{b}, \mathrm{c})=2+1=3 \Rightarrow \mathrm{L}(\mathrm{d}):=3, gán \mathrm{P}(\mathrm{d}):=\mathrm{b};

 

 

+Thực hiện bước 2:

\mathrm{L}(\mathrm{d})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=3

Suy ra:

v=d  và  \mathrm{T}:=\mathrm{T}-\{\mathrm{d}\}=\{c, e, z\}

+ Thực hiện bước 3: z \neq v, sang Bước 4.
+Thực hiện bước 4:
Xét đỉnh \mathrm{e} và đỉnh \mathrm{c} kề đỉnh \mathrm{d}. Ta có

\mathrm{L}(\mathrm{e}):=\infty>\mathrm{L}(\mathrm{d})+\mathrm{w}(\mathrm{d}, \mathrm{e})=3+3=6 \Rightarrow \mathrm{L}(\mathrm{e}):=6, \text { gán } \mathrm{P}(\mathrm{e}):=\mathrm{d}:

\mathrm{L}(\mathrm{c}):=9>\mathrm{L}(\mathrm{d})+\mathrm{w}(\mathrm{d}, \mathrm{c})=3+3=6 \Rightarrow \mathrm{L}(\mathrm{c}):=6, \text { gán } \mathrm{P}(\mathrm{c}):=\mathrm{d}:

+Thực hiện bước 2:

\mathrm{L}(\mathrm{e})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=6

Suy ra: v=e\mathrm{T}:=\mathrm{T}-\{\mathrm{e}\}=\{c, z\}

+ Thụ̣c hiện bước 3: z \neq v, sang bước 4.
+Thực hiện bước 4:
Xét đỉnh c và đỉnh \mathrm{z} kề đỉnh \mathrm{e}. Ta có
\mathrm{L}(\mathrm{c}):=6 : không đổi;
\mathrm{L}(\mathrm{z}):=\infty>\mathrm{L}(\mathrm{e})+\mathrm{w}(\mathrm{e}, \mathrm{z})=6+3=9 \Rightarrow \mathrm{L}(\mathrm{z}):=9, gán \mathrm{P}(\mathrm{z}):=\mathrm{e} ;

+Thực hiện bước 2:
\mathrm{L}(\mathrm{c})=\min \{\mathrm{L}(\mathrm{x}) \mid \mathrm{x} \in \mathrm{T}\}=6

Chọn 

Suy ra: v=c\mathrm{T}:=\mathrm{T}-\{\mathrm{e}\}=\{z\}

+ Thụ̣c hiện bước 3: z \neq v, sang bước 4.
+Thực hiện bước 4:
Xét đỉnh z  kề đỉnh \mathrm{c}. Ta có

Suy ra: v=z\mathrm{T}:=\mathrm{T}-\{\mathrm{z}\}
+ Thực hiện bước 3: z=v, kết thúc.
\mathrm{L}(\mathrm{z})=9 là độ dài đường đi ngắn nhất từ \mathrm{a} đến \mathrm{z}.
Vậy đường đi ngắn nhất là: \mathrm{a} \rightarrow \mathrm{b} \rightarrow \mathrm{d} \rightarrow \mathrm{e} \rightarrow \mathrm{c}  \rightarrow \mathrm{z}.