I.                   Phát biểu bài toán:

Có rất nhiều giải thuật đã được phát triển để giải bài toán tìm đường đi ngắn nhất giữa một cặp đỉnh, trong khuôn khổ bài viết này chúng tôi chỉ xin giới thiệu giải thuật Dijkstra. Giải thuật Dijkstra là một giải thuật để giải bài toán đường đi ngắn nhất nguồn đơn trên một đồ thị có trọng số cạnh mà tất cả các trọng số đều không âm.

Tìm đường đi ngắn nhất từ một đỉnh đến một đỉnh khác trong đồ thị liên thông có trọng số dương bằng thuật toán Dijkstra.

Ý tưởng:

• Tìm độ dài đường đi đến đỉnh gần a nhất, rồi đến đỉnh gần kế tiếp, …
• Sử dụng một tập hợp S chứa các đỉnh đã xét xong. Những đỉnh thuộc S là những đỉnh mà độ dài từ a đến nó đã được xác định
• Ở mỗi bước, chọn đỉnh u ”gần” nhất, thêm vào tập S và cập nhật độ dài đường đi qua các cạnh đi ra từ u
• Nhãn của đỉnh v: L_i(v)

Lưu trữ độ dài đường đi từ a đến v ở lần lặp thứ i

Những đỉnh thuộc S sẽ có nhãn cố định

L_k(v) = min { L_k-1(v); L_k-1(u) + w(uv) }

 II.                   Thuật toán

Xác định đường đi ngắn nhất giữa hai đỉnh cho trước, từ đỉnh a đến đỉnh b.

Ở mỗi đỉnh v, giải thuật Dijkstra xác định 3 thông tin: k_v, d_v và p_v.

• k_v: mang giá trị boolean xác định trạng thái được chọn của đỉnh v. Ban đầu ta khởi tạo tất cả các đỉnh v chưa được chọn, nghĩa là:

k_v = false, “ v Î V.

• d_v: là chiều dài đường đi mà ta tìm thấy cho đến thời điểm đang xét từ a đến v.

Khởi tạo, d_v = ¥,“v Î V {a}, d_a = 0.

• p_v: là đỉnh trước của đỉnh v trên đường đi ngắn nhất từ a đến b. Đường đi ngắn nhất từ a đến b có dạng {a,…,p_v,v,…,b}. Khởi tạo, p_v = null, “vÎ V.

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

B1. Khởi tạo: Đặt  k_v:= false “v Î V; d_v:= ¥,“v Î V {a}, d_a:=0.

B2. Chọn v Î V sao cho k_v = false  và d_v = min {d_t / tÎ V, k_t = false}

Nếu d_v = ¥ thì kết thúc, không tồn tại đường đi từ a đến b.

B3. Đánh dấu đỉnh v, k_v:= true.

B4. Nếu v = b thì kết thúc và d_blà độ dài đường đi ngắn nhất từ a đến b.

Ngược lại nếu v ¹ b sang B5.

B5. Với mỗi đỉnh u kề với v mà k_u = false, kiểm tra

Nếu d_u > d_v + w(v,u) thì d_u:= d_v + w(v,u)

Ghi nhớ đỉnh v: p_u:= v.

Quay lại B2.

III.               Độ phức tạp của thuật toán:

Gọi f(n) là số lần giải thuật Dijkstra khảo sát một cạnh của đồ thị G trong trường hợp xấu nhất. Khi đó ta có:

f(n) (|V|²)

Chứng minh: Cho n = |V|,  B5 là vòng lặp chứa các bước B2 ® B5, vòng lặp được thực hiện đến khi v = b.Vì ở mỗi vòng lặp ta rút ra một đỉnh của V và khởi đầu V có n phần tử, nên vòng lặp được xử lý nhiều nhất là n lần.

Ở B2 số đỉnh tối đa được khảo sát là n – 1 đỉnh

Ở B5 số đỉnh kề tối đa được khảo sát là n -1 đỉnh

Do đó:                 f(n) £ 2(n-1)n (|V|²)

Vậy độ phức tạp của giải thuật Dijkstra là O(|V|²).

IV. Demo

Download demo & source code:

http://goo.gl/N1wsKD