Giải Thuật Dijkstra - đề Tài CÀI đặt THUẬT TOÁN Tìm ĐƯỜNG đi ...

2.3.3.1 Nội dung

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 em 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. 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, dv và pv.

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.

Sau đây là các bước của giải thuật Dijkstra:

B1. Khởi tạo: Đặt kv:= false ∀v ∈ 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úc và dblà độ 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à ku = 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.

2.3.3.2 Độ phức tạp của giải thuật Dijkstra.

*** Trường hợp sử dụng ma trận kề.

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) < O(|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 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 < O(|V|2)

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

*** Trường hợp sử dụng danh sách kề

2.3.4 Lưu đồ thuật toán Dijstra Begin n, C = (cij), a, z L(a) = 0 L(v) = v a T(i) = 1 i n z T

Chọn v T sao cho L[v] đạt min T = T \ {v} x T & kề v L(x) = min(L(x), L(v) + c(v,x)) End S Đ S Đ L(z)

Chương 3:

KẾT QUẢ THỰC NGHIỆM 3.1 Khởi tạo

Tạo thuật toán tìm đường đi ngắn nhất, cài đặt chương trinh trên C# với đồ thị sau:

Cho đồ thị sau: 7 3 1 2 3 5 1 6 2 4 3 4 5 6

Tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 của đồ thị Sau khi cài đặt ta được chương trình như sau:

4 7

2 5

KẾT LUẬN

Qua thời gian làm thực tập cơ sở vừa qua, em đã tìm hiểu cơ bản về các khái niệm, cách biểu diễn đồ thị, và thuật toán tìm đường đi ngắn nhất trong đồ thị em thấy được ý nghĩa quan trọng của việc ứng dụng thuật toán vào bài toán trong thực tế. Em chọn ra thuật toán Dijkstra để cài đặt mô phỏng, với bài toán tìm đường đi ngắn nhất trong đồ thị theo thuật toán Dijkstra có những ứng dụng to lớn trong thực tế.

Tuy nhiên do hạn chế về trình độ, thời gian không nhiều nên những kết quả đạt được vẫn chưa đầy đủ, mặc dù đã cố gắng nhưng chương trình của em vẫn chưa hoàn chỉnh, còn nhiều hạn chế và có nhiều sai sót. Vấn đề ứng dụng còn nêu ra chung chung.

 Đạt được

Trong 5 tuần tìm hiểu, nghiên cứu và làm báo cáo cho đề tài của mình: “Cài đặt thuật toán tìm đường đi ngắn nhất trong đồ thị”. Với sự cố gắng của bản thân, sự chỉ

bảo tận tình của giáo viên hướng dẫn và sự trao đổi quý báu của bạn bè, bài báo cáo của em được hoàn thành với những nội dung:

+ Tư tưởng, các bước thực hiện của các thuật toán tìm đường đi ngắn nhất trong đồ thị + Cài đặt được chương trình chạy thuật toán tìm đường đi ngắn nhất trong đồ thị bằng ngôn ngữ C#

 Hạn chế

Sau quá trình thực hiện em thấy đề tài còn có nhiều hạn chế - Chương trình còn đơn giản

- Mô hình giao diện chương trình chưa có tính chuyên nghiêp.chưa có khả năng ứng dụng vào thực tế.

 Hướng phát triển

- Xây dựng giao diện chương trình có tính chuyên nghiệp hơn.

- Sau khi cài đặt chương trình thuật toán “tìm đường đi ngắn nhất trong đồ thị” bằng C#. Hướng tiếp theo của em là xây dựng ứng dụng xem bản đồ trực tuyến google map trên điện thoại di động…

Cuối cùng em xin chân thành cảm ơn toàn thể các thầy cô giáo, bạn bè, đã nhiệt tình giúp đỡ, động viên, ủng hộ em trong thời gian làm đề tài, đặc biệt là sự hướng dẫn nhiệt

tình của thầy giáo Bùi Anh Tú đã tận tình giúp đỡ và tạo điều kiện thuận lợi cho em để em có thể hoàn thành tốt đề tài này.

Em xin chân thành cảm ơn!

Thái Nguyên, Tháng 4 Năm 2013 Sinh Viên

Đỗ Thị Huyền

TÀI LIỆU THAM KHẢO

[1] Giáo trình Toán rời Rạc- Bộ môn Khoa học máy tính- Trường Đại học CNTT&TT Thái Nguyên-2010.

[2]Giáo trình Microsoft Visual Basic - Tác giả:Nguyễn Đăng Quang.

[3] Cuốn “khai phá Visual Basic.net với các bài lập trình căn bản- tác giả Nguyễn Gia Tuấn Anh – nhà xuất bản thanh niên.