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ại có 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ài toá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àm quen với những thuật toán kinh điển.
ậ ườ ế ể ể ả ắ ơ ấ ng đi ng n nh t gi a 2 đi m b t kỳ. Không m t ể ấ ộ ồ ị ữ ẽ ấ ậ ủ ạ ổ Dijkstra là thu t toán đ nh tuy n đ n gi n đ tìm đ tí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: ữ ườ ư ế ể ả ắ ấ
ớ ậ ng ho c vô h ặ ậ ạ ỉ ướ ọ ượ ấ ừ ỉ ị ồ ế ỉ ng). M i c nh ỗ ạ ướ ướ c g i là giá tr c a c nh. Cho tr c ị ủ ạ i c a G. đ nh v đ n các đ nh còn l ỉ ạ ủ ấ ng đi là nh nh t). ỏ ườ ế ạ ỉ ng đi này là đ ng đi có h Bài toán: Cho đ th G v i t p đ nh V và t p các c nh E (đ th có h ồ ị ồ ị c gán m t nhãn (giá tr không âm), nhãn này còn đ c a đ th đ ộ ủ ồ ị ượ m t đ nh xác đ nh v, g i là đ nh ngu n. Tìm đ ị ộ ỉ ọ v đ n các đ nh còn l (T c là tìm đ ng đi t ừ ườ ứ ng thì đ N u nh đ th có h ướ ư ồ ị ế ng đi ng n nh t t ắ ườ i v i t ng các giá c a các c nh trên đ ủ ạ ớ ổ ng. ườ ườ ướ
ị ợ ằ ộ ậ ồ ậ ả : Ta có th gi ể ả ỉ ế ấ ừ ả ị ế ằ ỉ ế ở ầ ấ ấ ỉ ỗ ằ ả ủ ể ng đi ng n nh t t ắ ế ủ ườ ẽ ả ộ ủ ồ ị ứ ạ thi ng đi ng n nh t nh v y mà ch đi qua các đ nh đã t n t s G có n đ nh và nhãn trên m i cung đ ả ử ộ đ l u đ dài c a đ ộ ầ ử ể ư ộ ấ ừ ỉ đ nh v đ n đ nh i, đ ế ị ườ ườ ỉ trong có S.
toán trên bài ế ồ : i thu t thì D[i] s l u đ dài đ đã i thu t d dàng, ta gi ả ậ ễ là gi đây D i ướ s các đ nh c a đ th đ ả ử i ả ỉ thu t ậ
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à Thu t toán Dijkstra ỉ ứ c ta s ẽ i m i b t. Kh i đ u S = { V }. Sau đó t nó đ n đ nh ngu n v đã bi kho ng cách ng n nh t t ỗ ướ ế ạ ắ t r ng m i cung có m t giá nó đ n v là ng n nh t. V i gi thêm vào S các đ nh mà kho ng cách t ộ ỗ ả ớ ắ ế ừ ỉ ồ ạ c m t đ i tr không âm thì ta luôn luôn tìm đ ỉ ư ậ ắ ộ ườ ượ trong S. Ð d dàng chi ti c l u trong i thu t, gi t hóa gi ượ ư ậ ả ể ễ m 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ì ta ố ị ứ v đ n cho C[i, j] =Ġ. Ta s dùng m t m ng D có n ph n t ế ấ ừ ỗ ướ m 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 c ở ầ ỗ ỉ ạ ng đi này ch đi qua các ng đi ng n nh t t c a gi ậ ỉ ắ ẽ ư ộ ả ủ đ nh ỉ c đánh s t 1 đ n n và đ nh ngu n là Ð cài đ t gi ỉ ặ ể ố ừ ủ ồ ị ượ i đ nh 1. gi đ Dijkstra ả ể ỉ
ồ ỉ ứ ỉ
ị
ấ ỏ
do
procedure Dijkstra; begin S := [1] ; { S ch ch a đ nh ngu n } for i:=2 to n do D[i] := C[1, i] ; { Kh i đ u các giá tr cho D } ở ầ for i:=1 to n - 1 do begin L 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 ộ ỗ ỉ D[u] := Min (D[u], D[w] + C[w, u]) ; end; end;
ế ấ ể ự ể ắ ồ i các đ nh trên đ ườ ỉ ộ ẽ ư ả đ nh ừ ỉ ướ ủ c c a ng đi ng n nh t đ có th xây d ng l ả ở ầ ườ ớ ọ i thu t Dijkstra i đ ạ ườ ữ ạ ỉ ớ ỉ ng đi ng n nh t. Lúc kh i đ u ta cho P[u] = 1, v i m i u khác 1. i nh sau : ư ắ ấ trên s đ ẽ ượ t l ế ạ ả ậ ở
ng đi này t N u mu n l u tr l ố ư ngu 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 ỉ ế đ nh w trên đ ỉ c vi Gi
