Để giải thích cách hoạt động của thuật toán Dijkstra trong mã qua ví dụ đồ thị bạn đã cung cấp, hãy xem xét các bước chi tiết từng bước khi thuật toán chạy:

Đồ thị Mẫu
Số đỉnh: 5 (đánh số từ 0 đến 4).

Số cạnh: 6.

Các cạnh với trọng số:

0 1 2 (cạnh từ đỉnh 0 đến đỉnh 1 với trọng số 2).
0 2 4 (cạnh từ đỉnh 0 đến đỉnh 2 với trọng số 4).
1 2 1 (cạnh từ đỉnh 1 đến đỉnh 2 với trọng số 1).
1 3 7 (cạnh từ đỉnh 1 đến đỉnh 3 với trọng số 7).
2 4 3 (cạnh từ đỉnh 2 đến đỉnh 4 với trọng số 3).
3 4 1 (cạnh từ đỉnh 3 đến đỉnh 4 với trọng số 1).
Đỉnh nguồn: 0.

Mô tả Thuật toán Dijkstra qua Ví dụ
Khởi tạo:

Đỉnh nguồn là 0.
Tạo mảng dist để lưu trữ khoảng cách ngắn nhất từ đỉnh nguồn 0 đến tất cả các đỉnh khác. Ban đầu, dist được thiết lập như sau:
dist[0] = 0 (khoảng cách từ đỉnh 0 đến chính nó là 0).
dist[1] = 1000000, dist[2] = 1000000, dist[3] = 1000000, dist[4] = 1000000 (khoảng cách đến tất cả các đỉnh khác ban đầu là vô cực).
Tạo hàng đợi ưu tiên pq và thêm đỉnh nguồn 0 với khoảng cách 0: pq = [(0, 0)].
Vòng lặp Thuật toán:

Lần lặp đầu tiên:

Lấy phần tử có khoảng cách nhỏ nhất từ hàng đợi pq, đó là (0, 0):
u = 0, d = 0.
Duyệt các đỉnh kề của u = 0:
Đỉnh 1: trọng số cạnh (0, 1) là 2.
dist[1] = min(1000000, 0 + 2) = 2.
Cập nhật dist[1] thành 2 và đẩy (2, 1) vào hàng đợi pq.
Đỉnh 2: trọng số cạnh (0, 2) là 4.
dist[2] = min(1000000, 0 + 4) = 4.
Cập nhật dist[2] thành 4 và đẩy (4, 2) vào hàng đợi pq.
Sau lần lặp này: pq = [(2, 1), (4, 2)].
Lần lặp thứ hai:

Lấy phần tử có khoảng cách nhỏ nhất từ hàng đợi pq, đó là (2, 1):
u = 1, d = 2.
Duyệt các đỉnh kề của u = 1:
Đỉnh 0: đã nằm trong tập đỉnh đã xử lý, bỏ qua.
Đỉnh 2: trọng số cạnh (1, 2) là 1.
dist[2] = min(4, 2 + 1) = 3.
Cập nhật dist[2] thành 3 và đẩy (3, 2) vào hàng đợi pq.
Đỉnh 3: trọng số cạnh (1, 3) là 7.
dist[3] = min(1000000, 2 + 7) = 9.
Cập nhật dist[3] thành 9 và đẩy (9, 3) vào hàng đợi pq.
Sau lần lặp này: pq = [(3, 2), (4, 2), (9, 3)].
Lần lặp thứ ba:

Lấy phần tử có khoảng cách nhỏ nhất từ hàng đợi pq, đó là (3, 2):
u = 2, d = 3.
Duyệt các đỉnh kề của u = 2:
Đỉnh 0: đã nằm trong tập đỉnh đã xử lý, bỏ qua.
Đỉnh 1: đã nằm trong tập đỉnh đã xử lý, bỏ qua.
Đỉnh 4: trọng số cạnh (2, 4) là 3.
dist[4] = min(1000000, 3 + 3) = 6.
Cập nhật dist[4] thành 6 và đẩy (6, 4) vào hàng đợi pq.
Sau lần lặp này: pq = [(4, 2), (9, 3), (6, 4)].
Lần lặp thứ tư:

Lấy phần tử có khoảng cách nhỏ nhất từ hàng đợi pq, đó là (4, 2):
u = 2, d = 4.
Đỉnh 2 đã được xử lý rồi, bỏ qua phần này.
Sau lần lặp này: pq = [(6, 4), (9, 3)].
Lần lặp thứ năm:

Lấy phần tử có khoảng cách nhỏ nhất từ hàng đợi pq, đó là (6, 4):
u = 4, d = 6.
Duyệt các đỉnh kề của u = 4:
Đỉnh 2: đã nằm trong tập đỉnh đã xử lý, bỏ qua.
Đỉnh 3: trọng số cạnh (4, 3) là 1.
dist[3] = min(9, 6 + 1) = 7.
Cập nhật dist[3] thành 7 và đẩy (7, 3) vào hàng đợi pq.
Sau lần lặp này: pq = [(7, 3), (9, 3)].
Lần lặp thứ sáu:

Lấy phần tử có khoảng cách nhỏ nhất từ hàng đợi pq, đó là (7, 3):
u = 3, d = 7.
Duyệt các đỉnh kề của u = 3:
Đỉnh 1: đã nằm trong tập đỉnh đã xử lý, bỏ qua.
Đỉnh 4: đã nằm trong tập đỉnh đã xử lý, bỏ qua.
Sau lần lặp này: pq = [(9, 3)].
Lần lặp thứ bảy:

Lấy phần tử có khoảng cách nhỏ nhất từ hàng đợi pq, đó là (9, 3):
u = 3, d = 9.
Đỉnh 3 đã được xử lý rồi, bỏ qua phần này.
Hàng đợi pq rỗng, thuật toán kết thúc.
Kết quả Cuối cùng
Thuật toán Dijkstra tính toán được khoảng cách ngắn nhất từ đỉnh 0 đến tất cả các đỉnh khác như sau:

dist[0] = 0: Khoảng cách từ 0 đến 0.
dist[1] = 2: Khoảng cách từ 0 đến 1 là 2.
dist[2] = 3: Khoảng cách từ 0 đến 2 là 3.
dist[3] = 7: Khoảng cách từ 0 đến 3 là 7.
dist[4] = 6: Khoảng cách từ 0 đến 4 là 6.
Kết quả này phù hợp với đồ thị mẫu và cách thức hoạt động của thuật toán Dijkstra.