ĐĂNG TIN
logo
Online:
Visits:
Stories:
Profile image
Tác giả: nguyenhaiblog
Trang tin cá nhân | Bài đã đăng
Lượt xem

Hiện tại:
1h trước:
24h trước:
Tổng số:
Thuật toán Dijsktra
Thursday, January 8, 2015 8:03
% of readers think this story is Fact. Add your two cents.


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: Li(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

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

Dijsktra_1

 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: kv, dvpv.

  • kv: 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à:

kv = false, v Î V.

  • dv: 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, dv = ¥,v Î V {a}, da = 0.

  • pv: 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,…,pv,v,…,b}. Khởi tạo, pv = null, “vÎ V.

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

B1. Khởi tạo: Đặt  kv:= falsev Î V; dv:= ¥,v Î V {a}, da:=0.

B2. Chọn v Î V sao cho kv = false  và dv = min {dt / tÎ V, kt = false}

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

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

B4. Nếu v = b thì kết thúcdblà độ 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 vku = false, kiểm tra

Nếu du > dv + w(v,u) thì du:= dv + w(v,u)

Ghi nhớ đỉnh v: pu:= 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|2)

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 Vn 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|2)

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

IV. Demo

Dijsktra_2

Download demo & source code:

http://goo.gl/N1wsKD

Tin nổi bật trong ngày
Tin mới nhất

Register

Newsletter

Email this story

If you really want to ban this commenter, please write down the reason:

If you really want to disable all recommended stories, click on OK button. After that, you will be redirect to your options page.