Tìm đường đi ngắn nhất với định tuyến Dijkstra

Bài viết này xin giới thiệu với các bạn mới làm quen với tin học và thuật giải một thuật toán đơn giản nhưng lạicó hiệu quả rất lớn trong việc tìm đường đi ngắn nhất trong đồ thị. Đó là thuật toán Dijkstra. Đây là thuật toánđã đăng tải trên tạp chí tin học & nhà trường từ những số đầu tiên nhưng bài viết này sẽ đăng tải đầy đủ về bàitoán, phương thức đưa ra thuật giải cũng như đoạn chương trình đầy đủ. Rất thích hợp với những bạn mới làmquen với những thuật toán kinh...
Nội dung trích xuất từ tài liệu:
Tìm đường đi ngắn nhất với định tuyến Dijkstra Tìm đường đi ngắn nhất với định tuyến Dijkstra Bàiviếtnàyxingiớithiệuvớicácbạnmớilàmquenvớitinhọcvàthuậtgiảimộtthuậttoánđơngiảnnhưnglại cóhiệuquảrấtlớntrongviệctìm đường đingắnnhấttrong đồthị. ĐólàthuậttoánDijkstra. Đâylàthuậttoán đãđăngtảitrêntạpchítinhọc&nhàtrườngtừnhữngsốđầutiênnhưngbàiviếtnàysẽđăngtảiđầyđủvềbài toán,phươngthứcđưarathuậtgiảicũngnhưđoạnchươngtrìnhđầyđủ.Rấtthíchhợpvớinhữngbạnmớilàm quenvớinhữngthuậttoánkinhđiển.Dijkstra là thuật toán định tuyến đơn giản để tìm đường đi ngắn nh ất gi ữa 2 đi ểm b ất kỳ. Không m ấttính tổng quát, ta coi mỗi điểm (nút mạng) là một đỉnh c ủa một đồ thị, ta sẽ dùng thu ật toán Dijkstra đ ểgiải quyết bài toán tìm đường đi ngắn nhất giữa 2 điểm như sau:Bài toán: Cho đồ thị G với tập đỉnh V và tập các cạnh E (đ ồ th ị có h ướng ho ặc vô h ướng). M ỗi c ạnhcủa đồ thị được gán một nhãn (giá trị không âm), nhãn này còn đ ược gọi là giá tr ị c ủa c ạnh. Cho tr ướcmột đỉnh xác định v, gọi là đỉnh nguồn. Tìm đường đi ngắn nh ất t ừ đ ỉnh v đ ến các đ ỉnh còn l ại c ủa G.(Tức là tìm đường đi từ v đến các đỉnh còn lại với tổng các giá c ủa các c ạnh trên đ ường đi là nh ỏ nh ất).Nếu như đồ thị có hướng thì đường đi này là đường đi có hướng.Thuật toán Dijkstra: Ta có thể giải bài toán bằng cách xác định m ột t ập h ợp S ch ứa các đ ỉnh màkhoảng cách ngắn nhất từ nó đến đỉnh nguồn v đã bi ết. Khởi đầu S = { V }. Sau đó t ại m ỗi b ước ta s ẽthêm vào S các đỉnh mà khoảng cách từ nó đến v là ngắn nh ất. V ới gi ả thi ết r ằng m ỗi cung có m ột giátrị không âm thì ta luôn luôn tìm được một đường đi ngắn nhất như v ậy mà ch ỉ đi qua các đ ỉnh đã t ồn t ạitrong S. Ðể dễ dàng chi tiết hóa giải thuật, giả sử G có n đỉnh và nhãn trên m ỗi cung đ ược l ưu trongmảng C, tức là C[i, j] bằng giá trị(có thể xem là độ dài) của cung (i, j). N ếu i và j không có cung n ối thì tacho C[i, j] =Ġ. Ta sẽ dùng một mảng D có n phần t ử để l ưu đ ộ dài c ủa đ ường đi ng ắn nh ất t ừ v đ ếnmỗi đỉnh của đồ thị. Khởi đầu thì giá trị này chính là đ ộ dài c ạnh (v, i), t ức D[i] = C[v, i]. T ại m ỗi b ướccủa giải thuật thì D[i] sẽ lưu độ dài đường đi ngắn nhất từ đỉnh v đến đỉnh i, đường đi này chỉ đi qua cácđỉnh đã có trong S.Ðể cài đặt giải thuật dễ dàng, ta giả sử các đỉnh c ủa đ ồ th ị đ ược đánh s ố t ừ 1 đ ến n và đ ỉnh ngu ồn làđỉnh Dưới giải thuật để giải 1. đây là Dijkstra bài toán trên :procedure Dijkstra;beginS := [1] ; { S chỉ chứa đỉnh nguồn }for i:=2 to n doD[i] := C[1, i] ; { Khởi đầu các giá trị cho D }for i:=1 to n - 1 dobeginLấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ;Thêm w vào S ;for mỗi đỉnh u thuộc V - S doD[u] := Min (D[u], D[w] + C[w, u]) ;end;end;Nếu muốn lưu trữ lại các đỉnh trên đường đi ngắn nhất để có thể xây dựng lại đường đi này từ đỉnhnguồn đến các đỉnh khác, ta dùng một mảng P. Mảng này sẽ lưu P[u] = w với đỉnh u là đỉnh trước củađỉnh w trên đường đi ngắn nhất. Lúc khởi đầu ta cho P[u] = 1, với mọi u khác 1.Giải thuật Dijkstra ở trên sẽ được viết lại như sau :procedure Dijkstra ;beginS := [1] ; { S chỉ chứa đỉnh nguồn }for i:=2 to n dobeginD[i] := C[1, i] ; { Khởi đầu các giá trị cho D }P[i] := 1 ; { Khởi đầu các giá trị cho P }end ;for i:=1 to n - 1 dobeginLấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ;Thêm w vào S ;for mỗi đỉnh u thuộc V - S doif (D[w] + C[w, u] < D [u]) thenbeginD[u] := D[w] + C[w, u] ; P[u] := w ;end ;end;end;Ví dụ : Áp dụng giải thuật Dijkstra cho đồ thị hình sau:procedure DijksTra; begint:=false;t[u0]:=true;d[i]:=c[u0,i];{Neu khong co duong di thi d[i]=i’}k:=1;{Da ket nap duoc 1 dinh}while kdobegin{Tim min}min:=i’;for i:=1 to n doif (d[i]d[u]+c[u,i] thenif not((d[i]=i’)and(d[u]=i’)and(c[u,i]=i’)) thenbegind[i]:=d[u]+c[u,i];truoc[i]:=uendend;if d[v0]=i’ thenKhongCoDuongDielseQuayLaiMangTruocDeTimDuongend;