Thuật Toán Dijsktra - Prim

LỜI NÓI ĐẦU

Bài toán tối ưu là một bài toán muôn thuở trong tin học bởi nó có ứng dụng thực tế cao. Ví dụ như làm thế nào để hoàn thành một công việc nào đó với chi phí ít nhất, hay đi như thế nào để đến đích sớm nhất,v.v. Cùng với sự trợ giúp của máy tính và các thuật toán hiệu quả đã giúp chúng ta giải quyết bài toán tối ưu một cách dễ dàng và chính xác. Một trong số các thuật toán hiệu quả đó là thuật toán Dijkstra - thuật toán tìm đường đi ngắn nhất và thuật toán Prim – Thuật toán tìm cây khung nhỏ nhất trên đồ thị có trọng số không âm. Trong bài viết này chúng tôi chỉ nghiên cứu trên đồ thị vô hướng có trọng số không âm.
Với trình độ lý luận còn thiếu chặt chẽ, kiến thức thực tiễn còn non yếu nên chắc chắn còn nhiều sai sót. Do vậy chúng tôi mong nhận được sự giúp đỡ bổ sung khiếm khuyết của quý thầy cô giáo, cùng các bạn trong lớp tạo điều kiện cho bài tìm hiểu này được hoàn chỉnh hơn. Tôi xin chân thành cảm ơn sự giúp đỡ tận tình của thầy giáo Hồ Hữu Linh và tất cả các bạn.

Sinh viên thực hiện:
Nguyễn Thanh Nhựt












PHẦN I:
GIẢI THUẬT_LƯU ĐỒ THUẬT TOÁN DIJKSTRA

Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra, là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị không có cạnh mang trọng số âm.
1. Phân tích.
Dùng ma trận kề để biểu diễn đồ thị C= (cij), cij = trọng số của cung (i,j), cij =+ ∞ nếu không có cung (i,j). Một mảng d[] để ghi các độ dài đường đi ngắn nhất từ s tới đỉnh i đang có . Xuất phát d[s] =0 và d[i] =c
nếu i kề s, d[j] =+ ∞ nếu j không kề s.
2 Giải thuật tìm đường đi ngắn nhất giữa một cặp đỉnh.
Định nghĩa 1.0.
Xét đồ thị có trọng số cạnh G = (V,E,(), với hàm trọng số (:E( R là ánh xạ từ tập các cạnh E đến tập số thực R.
Định nghĩa 1.1. Đường đi p từ đỉnh u đến đỉnh v là dãy các cạnh nối tiếp nhau bắt đầu từ đỉnh u kết thúc tại đỉnh v. Đường đi p từ u đến v được biểu diễn như sau: p=(u=v0,v1…,vk=v)
Định nghĩa 1.2. Độ dài của đường đi p = ( v0,v1,...,vk ), ký hiệu ((p), là tổng các trọng số của các cạnh trên đường đi:
((p) =

Định nghĩa 1.3. Gọi ((u,v) là tập tất cả đường đi từ u đến v. Độ dài đường đi ngắn nhất từ đỉnh u đến đỉnh v được xác định bởi:
d(u,v) =

Định nghĩa 1.4. Đường đi ngắn nhất pmin(u,v) từ đỉnh u đến đỉnh v là đường đi có độ dài d(u,v).

3 Giải thuật Dijkstra.
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 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. 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