Bài toán

Cho G = (V,E) là đơn đồ thị liên thông (vô hướng hoặc có hướng) có trọng số

V = {1,.., n} là tập các đỉnh , E là tập các cạnh (cung).

Cho s₀ € E. Tìm đường đi ngắn nhất đi từ s₀ đến các đỉnh còn lại. Giải bài toán trên bằng thuật toán Dijkstra .

Phân tích, thiết kế thuật toán

Thuật toán Dijkstra cho phép tìm đường đi ngắn nhất từ một đỉnh s đến các đỉnh còn lại của đồ thị và chiều dài (trọng số ) tương ứng. Phương pháp của thuật toán là xác định tuần tự đỉnh có chiều dài đến s theo thứ tự tăng dần. Thuật toán được xây dựng trên cơ sở gán cho mỗi đỉnh các nhãn tạm thời. Nhãn tạm thời của các đỉnh cho biết cận trên của chiều dài đường đi ngắn nhất từ s đến đỉnh đó. Nhãn của các đỉnh sẽ biến đổi trong các bước lặp, mà ở mỗi bước lặp sẽ có một nhãn tạm thời trở thành chính thức. Nếu nhãn của một đỉnh nào đó trở thành chính thức thì đó cũng chính là chiều dài ngắn nhất của đường đi từ s đến đỉnh đó.

Ký hiệu :

* L(v) để chỉ nhãn của đỉnh v, tức là cận trên của chiều dài đường đi ngắn

nhất từ s0 đến v.

* d(s0 ,v) : chiều dài đường đi ngắn nhất từ s0 đến v.

* m(s0 ,v) là trọng số của cung (cạnh) (s,v).

Thuật toán Dijkstra tìm chiều dài đường đi ngắn nhất từ đỉnh s đến n-1 đỉnh

còn lại được mô tả như sau:

input: G, s0

Output : d(s0,v), mọi v ≠ s0 ;

Mô tả :

o Khởi động :

L(v) = ∞ , mọi v ≠ s0; //Nhãn tạm thời

S = {s₀}; //Tập lưu trữ các đỉnh có nhãn chính thức

o Bước 0 :

d(s0 ,s0 ) = L(s0) = 0;

S = {s0}; // s0 có Nhãn chính thức

o Bước 1:

- Tính lại nhãn tạm thời L(v), v không thuộc S :

Nếu v kề với s0 thì

L(v) = Min{L(v), L(s0) + m(s0,v)};

- Tìm s1 thuộc S và kề với s0 sao cho :

o Bước 2:

- Tính lại nhãn tạm thời L(v), v? S :

Nếu v kề với s1 thì L(v) = Min{L(v), L(s1) + m(s1,v)};

Tính chất tham lam của thuật toán Dijkstra là tại mỗi bước, chọn si không thuộc S và si là đỉnh kề với sj, với j = 0,i-1 sao cho L(si ) = Min{L(v) : v ? S }. Minh hoạ : Xét đồ thị có hướng G :

Đường đi ngắn nhất từ đỉnh s = 1 đến các đỉnh còn lại :

Bảng các bước đi.