MÔ HÌNH ĐƯỜNG ĐI NGẮN NHẤT

MÔ HÌNH ĐƯỜNG ĐI NGẮN NHẤT

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

a. Bài toán đường đi ngắn nhất

Mô hình đường đi ngắn nhất xác định đường có chiều dài ngắn nhất nối 2 nút của một mạng. Bài toán đường đi ngắn nhất thường gặp là xác định lộ trình có chiều dài ngắn nhất giữa 2 nút trong một mạng giao thông. Tuy nhiên bài toán có thể mở rộng thành nhiều bài toán thực tế.

b. Giải thuật đường đi ngắn nhất

Các giải thuật đường đi ngắn nhất thường dùng là:

Giải thuật Dijkstra
Giải thuật Floyd

Giải thuật Dijkstra cho phép xác định đường đi ngắn nhất từ một nút nguồn đến một nút đích bất kỳ trong mạng. Giải thuật Floyd, tổng quát hơn, cho phép xác định đường đi ngắn nhất giữa 2 nút bất kỳ của mạng.

c. Giải thuật Dijkstra.

Gọi nút nguồn của mạng là nút 1, gọi u_i là khoảng cách ngắn nhất từ nút ngùôn 1 đến nút i của mạng và d_ij là khoảng cách từ nút i đến nút j.

Từ nút i với nút kế tiếp là nút j, ta dán nhãn cho nút j như sau:

[u_j , i] = [u_i + d_ij, i] , dij ³ 0

Thấy rằng nút đầu tiên là nút không có nút kế trước nên có nhãn là [0, -]. Nhãn của 1 nút có thể là nhãn tạm thời hay nhãn cố định. Nhãn nút là tạm thời và sẽ thay đổi khi tìm được đường đi có khoảng cách ngắn hơn đến nút. Nhãn nút sẽ chuyển thành cố định khi không thể tìm được đường đi có khoảng cách ngắn hơn đến nút.

Các bước của giải thuật Dijkstra:

Bước 0:

Dán nhãn cố định cho nút nguồn 1 là [0, -].
Đặt i=1

Bước i: Từ nút có nhãn cố định i

Dán nhãn [u_i + d_ij, i] cho các nút kế tiếp j của i nếu các nút này chưa có nhãn cố định.
Nếu một nốt kế tiếp j đã có nhãn là [u_j, k] và u_i + d_ij < u_j thì thay nhãn [u_j, k] bởi nhãn [u_i + d_ij, i].
Nếu có nút mạng chưa dán nhãn cố định thì chọn trong số các nhãn tạm thời nhãn [u_r,s] có khoảng cách u_rngắn nhất. Đặt i = r, quay lại bước i.
Nếu mọi nút mạng đều dán nhãn cố định thì dừng.