Dijtra - thuật toán tốt để giải các bài toán tối ưu
Đỗ Giang Lâm
Bài toán tối ưu là một bài toán muôn thuở trong tin học bởi nó có ứng dụng thực tế cao. Ví
dụ như làm thế nào để hoàn thành một công viêc nào đó với chi phí ít nhất, hay đi như thế
nào để đến đích sớm nhất, vv... Cùng với sự trợ giúp của máy tính và các thuật toán hiệu
quả đã giúp chúng ta giải quyết bài toán tối ưu một cách dễ dàng và chính xác. Một trong
số các thuật toán hiệu quả đó là thuật toán Dijkstra- thuật toán tìm đường đi ngắn nhất
trên đồ thị có trọng số không âm.
Chắc hẳn các bạn đều không xa lạ gì với thuật toán Dijkstra. Đây là một cải tiến từ thuật
toán Ford_Bellman. Trong truờng hợp trọng số trên các cung là không âm, thuật toán do
Dijkstra đề nghị để giải bài toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của
đồ thị làm việc hiểu quả hơn nhiều so với thuật toán Ford_Bellman. Thuật toán được xây
dựng trên cơ sở gán cho các đỉnh các nhãn tạm thời. Nhãn của một đỉnh cho biết cận trên
của độ dài đường đi ngắn nhất từ s đến nó. Các nhãn này sẽ được biến đổi theo một thủ tục
lặp, mà ở mỗi một bước lặp có một nhãn tạm thời trở thành nhãn cố định. Nếu nhãn của
một đỉnh nào đó trở thành nhãn cố định thì nó sẽ cho ta không phải là cận trên mà là đường
đi ngắn nhất từ đỉnh s đến nó. Thuật toán được mô tả cụ thể như sau:
Đầu vào: Đồ thị có hướng G = (V,E) với n đỉnh, s thuộc V là đỉnh xuất phát, ma trận trọng
số a[u,v], a[u,v] ≥ 0, u,v thuộc V.
Đầu ra: Độ dài đường đi ngắn nhất từ s đến tất các đỉnh còn lại: d[v], v thuộc V.
truoc[v], v thuộc V, ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v
Procedure Dijkstra;
Begin
for v thuộc V do begin d[v] := a[s,v]; truoc[v] := s; end; (* Khởi tạo *)
d[s] := 0; T := V {s} (* T là tập các đỉnh có nhãn tạm thời *)
(* Bước lặp *)
while T ≠ ∅ do
Begin
Tìm đỉnh u thuộc T thoả mãn d[u] = Min {d[z] : z thuộc T}
T := T{u} (* Cố định nhãn của đỉnh u *)
for v thuộc T do (* Cập nhật lại nhãn cho các đỉnh trong T *)

Hãy tìm cách hướng dẫn rôbốt thực hiện các thao tác để đưa kiện hàng $ về vị trí @ sao
cho số công phải dùng là ít nhất.
Dữ liệu: Vào từ file văn bản CARGO.INP
- Dòng 1: Ghi ba số nguyên dương m, n, C ( m, n ≤ 100; C ≤ 100)
- m dòng tiếp theo, dòng thứ i ghi đủ n ký kiệu trên hàng i của bản đồ theo đúng thứ tự trái
qua phải.
Các ký hiệu được ghi liền nhau.
Kết quả: Ghi ra file văn bản CARGO.OUT
- Dòng 1: Ghi số công cần thực hiện
- Dòng 2: Một dãy liên tiếp các ký tự thuộc {L, R, U, D, +, -} thể hiện các động tác cần
thực hiện của rô bốt.
Rằng buộc: Luôn có phương án thực hiện yêu cầu đề bài.
Ví dụ:
Phân tích:
Thuật toán: Ta sẽ dùng thuật toán Dijkstra để giải bài toán này.
* Mô hình đồ thị:
Mỗi đỉnh của đồ thị ở đây gồm 3 trường để phân biệt với các đỉnh khác:
- i: Tọa độ dòng của kiện hàng (i = 1..m)
- j: Tọa độ cột của kiện hàng (j = 1..n)
- h: Hướng của rô bốt đứng cạnh kiện hàng so với kiện hàng (h = 1..4: Bắc, Đông, Nam,
Tây).
Bạn có thể quan niệm mỗi đỉnh là (i,j,u,v): trong đó i,j: tọa độ của kiện hàng; u,v: tọa độ
của rôbốt đứng cạnh kiện hàng. Nhưng làm thế sẽ rất lãng phí bộ nhớ và không chạy hết
được dữ liệu. Ta chỉ cần biết hướng h của rôbốt so với kiện hàng là có thể tính được tọa độ
của rôbốt bằng cách dùng 2 hằng mảng lưu các số ra:
dx : array[1..4] of integer = (-1,0,1,0)
dy : array[1..4] of integer = (0,1,0,-1)
Khi đó, tọa độ(u,v) của rôbốt sẽ là : u := i + dx[h]; v := j + dy[h];
- Hai đỉnh (i1,j1,h1) và (i2,j2,h2) được gọi là kề nhau nếu qua 1 trong 2 thao tác + hoặc -
kiện hàng được rôbốt đẩy hoặc kéo từ ô (i1, j1) đến ô (i2, j2) và rôbốt có thể di chuyển

xuất phát và 1 điểm kết thúc. Luôn có đường đi từ điểm xuất phát đến điểm kết thúc. Luôn
có một khung gồm toàn ký tự ’.’ viền bản đồ để không thể vượt ra ngoài bản đồ.
Dữ liệu: Vào từ file văn bản ERP.INP gồm các dòng:
- Dòng thứ nhất chứa 2 số nguyên dương h, w theo thứ tự là chiều cao h và chiều rộng của
bản đồ.
- Mỗi dòng trong h dòng tiếp theo chứa w ký tự. Mỗi ký tự chỉ là một trong số các ký tự
sau:
- ’.’: vị trí không có đường
- ’#’: vị trí có đường của bản đồ.
- ’E’: vị trí xuất phát, xe hướng đầu về phía Đông.
- ’W’: vị trí xuất phát, xe hướng đầu về phía Tây.
- ’N’: vị trí xuất phát, xe hướng đầu về phía Bắc.
- ’S’: vị trí xuất phát, xe hướng đầu về phía Nam.
- ’F’: vị trí kết thúc.
Trong bản đồ có đúng 1 trong 4 ký tự ’E’, ’W’, ’N’, ’S’. Và đúng 1 ký tự F.
Kết quả ghi ra file văn bản ERP.OUT duy nhất một số là lệ phí của lộ trình rẻ nhất đi từ vị
trí xuất phát đến vị trí kết thúc.
Phân tích:
Mô hình đồ thị:
Mỗi đỉnh của đồ thị ở đây gồm 3 trường để phân biệt với các đỉnh khác:
- i: Tọa độ dòng của nút mà ô tô đang đứng( i = 1..h)
- j: Tọa độ cột của nút mà ô tô đang đứng (j = 1..w)
- h: Hướng của đầu ô tô (h=1..4)
Ta sẽ xét xem 1 ô (i,j) có phải là 1 nút không. Để dễ hình dung, ta sẽ quan niệm 1 nút ở đây
cũng giống như 1 nút giao thông như trong thực tế. Ta sẽ xây dựng một mảng nut
(nut(i,j)=true: ô (i,j) là 1 nút ) như sau:
- Điều kiện cần để ô (i,j) là 1 nút là ô (i,j) đó phải là đường.
- Các ô xuất phát và kết thúc đều là nút.
- Nếu một ô (i,j) có 2 ô kề theo hướng 1 và 3 (hoặc 2 và 4) là đường và 2 ô kề theo hướng
2 và 4 (hoặc 1 và 3) không là đường thì ô (i,j) đó không là 1 nút. Ngược lại ô (i,j) đó là 1

- Các dòng tiếp theo ghi ma trận trạng thái của các ô gồm M dòng, N cột, trong đó giá trị
dòng i cột j mô tả trạng thái của ô [i,j].
Các giá trị ghi trên 1 dòng cách nhau ít nhất 1 dấu cách.
Kết quả ghi ra file văn bản MECUNG.OUT:
1. Trường hợp tìm thấy đường đi:
- Dòng đàu ghi sô ô mà đường đi đi qua
- Dòng tiếp theo ghi thông tin về đường đi gồm tọa độ dòng xuất phát, sau đó cách 1 dấu