Thuật Toán Tìm đường đi Ngắn Nhất - Tài Liệu đại Học

Tài liệu đại học Toggle navigation

• Miễn phí (current)
• Danh mục
  • Khoa học kỹ thuật
  • Công nghệ thông tin
  • Kinh tế, Tài chính, Kế toán
  • Văn hóa, Xã hội
  • Ngoại ngữ
  • Văn học, Báo chí
  • Kiến trúc, xây dựng
  • Sư phạm
  • Khoa học Tự nhiên
  • Luật
  • Y Dược, Công nghệ thực phẩm
  • Nông Lâm Thủy sản
  • Ôn thi Đại học, THPT
  • Đại cương
  • Tài liệu khác
  • Luận văn tổng hợp
  • Nông Lâm
  • Nông nghiệp
  • Luận văn luận án
  • Văn mẫu
• Luận văn tổng hợp

1. Home
2. Luận văn tổng hợp
3. thuật toán tìm đường đi ngắn nhất

Trich dan thuật toán tìm đường đi ngắn nhất - Pdf 24

Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng LỜI NÓI ĐẦU Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đờivà có nhiều ứng dụng hiện đại.Những tư tưởng cơ bản của lý thuyết đồ thị đươc đề xuất từ những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler.Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thàng phố Konigsberg.Đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau .Chẳng hạn , đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện.Chúng ta có thể phân biệt các hợp chất hoá học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị.Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tinđược với nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán như : tìm đường đi ngắn nhất giữa hai thành phố trong cùng một mạng giao thông . Chúng ta còn sử dụng đồ thị để giải các bài toán về lập lịch,thời khoá biểu,và phân bố tần số cho các trạm phát thanh và truyền hình Mục đích ta tìm hiểu là nhằm giới thiệu các khái niệm cơ bản,các bài toán ứng dụng quan trọng của lý thuyết đồ thị như bài toán cây khung nhỏ nhất , bài toán tìm đường đi ngắn nhất và những thuật toán để giải quyết chúng đã được trình bày chi tiết cùng với việc phân tích và hướng dẫn cài đặt chương trình trên máy tính.Củng cố và rèn luyện kỹ năng lập trình, nhớ lại các thuật toán mà đặc biệt là thuật toán Dijkstra.Chương 1 : Lý thuyết về thuật toán tìm đường đi ngắn nhất.Chương 2 : Xây dựng thuật toán. Chương 3 : Cài đặt thuật toán.http://vuson.tk - Trang 1 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng Đồ án cơ sở GVHD: Đoàn Văn Thắng Hà Tây Đồng Nai Huế An Giang Hà Nội HCM Bình ĐịnhQuãng Ngãi Phú Yên Khánh HòaHình 2. Sơ đồ mạng máy tính với đa kênh thoạiĐịnh nghĩa 2. Đa đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh , và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh .Haicạnh e1 va e2 được gọi là cạnh lặpnếu chúng cùng tương ứng với một cặp đỉnh.Hà Tây Đồng Nai Huế An Giang Hà Nội TPHCM Bình ĐịnhQuãng Ngãi Phú Yên Khánh HòaHình 3. Sơ đồ mạng máy tính với kênh thông báo.Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị, vì trong đa đồ thị có hai hay nhiều hơn cạnh nối một cặp đỉnh nào đó.Trong mạng máy tính có thể có những kênh thoại nối một máy tính nào đó với chính nó(chẳng hạn với mục đích thông báo).Mạng như vậy được cho trong hình 3.Như vậy đa đồ thị không thể mô tả được mạng như vậy, bởi vì có những khuyên (cạnh nối một đỉnh vói chính nó).Trong trường hợp này chúng ta cần sử dụng đến khái niệm giả đồ thị vô hướng, được định nghĩa như sau:http://vuson.tk - Trang 3 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368I.1.2. Các thuật ngữ cơ bảnhttp://vuson.tk - Trang 4 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng Trong mục này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ thị.Trước tiên ,ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hướng.Định nghĩa 1. Hai đỉnh u va v của đồ thị có hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G.Nếu e=(u,v) là cạnh của đồ thị thì ta nói cạnh này là cạnh liên thuộc với hai đỉnh u và v, hoặc cũng nói là cạnh e nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u,v).Để có thể biết có bao nhiêu cạnh liên thuộc với một đỉnh , ta đưa vào định nghĩa sau :Định nghĩa 2. Ta gọi bậc của đỉnh v trong đồ thị vô hướnglà số cạnh liên thuộc với nó ta sẽ kí hiệu là deg(v).b c d a f e gHình 1. Đồ thị vô hướngThí dụ . Xét đồ thị cho trong hình 1, ta códeg(a)=1, deg(b)=4 , deg(c)=4 , deg(f)=3, deg(d)=1 ,deg(e)=3 , deg(g)=0.Đỉnh bậc 0 gọi là đỉnh cô lập , đỉnh bậc 1 được gọi là đỉnh treo .Trong ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau :Định lý 1. Giả sử G=(V,E) là đồ thị vô hướng với m cạnh . Khi đó2m=∑ deg(v) v ∈ VChứng minh. Rõ ràng trong mỗi cạnh e=(u,v) được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh +(v)(deg-(v)). a b c e dHình 2. Đồ thị có hướng GThí dụ 3. Xét đồ thị cho trong hình 2. Ta códeg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e)=2.deg+(a)=3, deg+(b)=1 deg+(c)=1, deg+(d)=2, deg+(e)=2ntrong đó u=x0 , v=xn , ( xi , xi+1 ) ∈E , i= 0, 1, 2 , , n-1.Đường đi nói trên còn có thể biểu diễn dưới dạng các cạnh:(x0 , x1 ) , ( x1 , x2), , ( xn-1 , xn ).Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối ( tức là u=v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.Thí dụ 1. Trên đồ thị vô hướng cho trong hình 1: a,d,c,f,e là đường đi đơn độ dài A , i= 0, 1, 2 , , n-1.Đường đi nói trên còn có thể biểu diễn dưới dạng các cung:http://vuson.tk - Trang 7 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng (x0 , x1 ) , ( x1 , x2), , ( xn-1 , xn ).Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối ( tức là u=v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cung nào bị lặp lại.Thí dụ 2. Trên đồ thị có hướng cho trong hình 1: a,d,c,f,e là đường đi đơn độ dài 4. Còn d,e,c,a không là đường đi do (e,c) không phải là cung của đồ thị. Dãy b,c,f,e,b là chu trình độ dài 4. Đường đi a,b,e,d,a,b có độ dài là 5 không phải là đường đi đơn, do cung (a,b) có mặt trong nó hai lần.Xét một mạng máy tính .Một câu hỏi đặt ra là hai máy tính bất kỳ trong mạng này có thể trao đổi được thông tin với nhau hoặc trực tiếp qua kênh nối chúng hợăc thông qua một hoặc vài máy tính trung gian trong mạng? Nếu sử dụngđồ thị để biểu diễn mạng máy tính này (trong đó các đỉnh của đồ thị tương ứng vớicác máy tính , còn các cạnh tương ứng với các kênh nối) câu hỏi đó được phát ⊆Ehttp://vuson.tk - Trang 8 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng Trong trường hợp đồ thị là không liên thông , nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị.Thí dụ 4. Đồ thị H trong hình 2 gồm 3 thành phần liên thông là H1,H2,H3.Trong mạng máy tính có thể có những máy ( những kênh nối ) mà sự hỏng hóc của nó có thể ảnh hưởng đến việc trao đổi thông tin trong mạng. Các khái niệm tương ứng với tình huống này được đưa ra trong định nghĩa sau.Định nghĩa 5. Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị .Thí dụ 5. trong đồ thị G ở hình 2, đỉnh d và e là đỉnh rẽ nhánh, còn các cạnh (d,g) và (e,f) là cầu.Đối với đồ thị có hướng có hai khái niệm liên thông phụ thuộc vào việc ta có xét đến hướng trên các cung hay không.Định nghĩa 6. Đồ thị có hướng G=(V,A) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.Định nghĩa 7. Đồ thị có hướng G=(V,A) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị vô hướng liên thông.Rõ ràng nếu đồ thị là liên thông mạnh thì nó cũng là liên thông yếu, nhưng điều cạnh chưa được định hướng của C’ theo một hướng dọc theo chu trình này( không định hướng lại các cạnh đã có hướng). Thủ tục trên sẽ được lặp lại cho đến khi tất cả các cạnh của đồ thị được định hướng. Khi đó ta thu được đồ thị có hướng liên thông mạnhI.2 Các khái niệm mở đầu về đề tài cần đề cập tớiI.2.1 Mở đầuTrong phần này chúng ta chỉ xét đồ thị có hướng G=(V,E) và |V|=n,|E|=m với các cung được gán trọng số, nghĩa là , mỗi cung (u,v)∈E của nó được đặt tương ứng với một số thực a(u,v) gọi là trọng số của nó.Chúng ta sẽ đặt a(u,v)=∞, nếu (u,v)∉E .Nếu dãy v0, v1 , , vp là một đường đi trên G, thì độ dài của nó được định nghĩa là tổng sau: p∑a(vi-1, vinhất từ s đến t, trong trường hợp trọng số không âm, có thể tìm một cách dễ dàng.Để tìm đường đi , chỉ cần chú ý là đối với cặp đỉnh s,t∈V tuỳ ý (s≠t) luôn tìmđược đỉnh v sao cho:d(s,t) = d(s,v) + a(v,t)Thực vậy đỉnh v như vậy chính là đỉnh đi trước đỉnh t trong đường đin ngắn nhấttừ s đến t Tiếp theo ta có thể tìm được u sao cho d(s,v)=d(s,u)+a(u,v), Từ giảthiết về tính không âm của các trọng số dễ dàng suy ra rằng dãy t,v,u không chứađỉnh lặp lại và kết thúc ở đỉnh s.Rõ ràng dãy thu được xác định đường đi ngắn nhấttừ s đến t.I.2.2 Đường đi ngắn nhất xuất phát từ một đỉnhPhần lớn các thuật toán tìm khoảng cách giữa hai đỉnh s và t được xây dựngnhờ kỹ thuật tính toán mà ta có thể mô tả đại thể như sau: từ ma trận trọng số a[u,v],u,v∈V,ta tính cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v∈V.Mỗi khi phát hiệnd[u]+a[u,v]<d[v] (1)cận trên d[v] sẽ được tốt lên : d[v]=d[u]+a[u,v].Quá trình đó sẽ kết thúc khi nào chúng ta không làm tốt thêm được bất cứ cận trên nào.Khi đó, rõ ràng giá trị của mỗi d[v] sẽ cho ta khoảng cách từ mỗi đỉnhs đến v. Khi thể hiện kỹ thuật tính toán này trên máy tính, cận trên d[v] sẽ được gọi là nhãn của đỉnh v,còn việc tính lại các cận trên này sẽ gọi là phép gán nhãn cho đồ thị và toàn bộ thủ tục thường gọi là thủ tục gán nhãn. Nhận thấy rằng để tính khoảng cách từ s đến tất cả các đỉnh còn lại của đồ thị.Hiện nay vẫn chưa biết thuật toán nào cho phép tìm đường đi ngắn nhất giữa hai đỉnh làm việc thực sự VĐầu ra : khoảng cách từ đỉnh s đến tất cả các đỉnh còn lại d[v],v∈V.*)Begin(*khởi tạo*)For v∈V. do Begind[v]:=a[s, v];Truoc [v]:=s;End;d[s]:=0;T:=V\{s};(* T là tập các đỉnh có nhãn tạm thời *)(*Bước lặp*)While T∅≠ doBegin Tim dinh u∈T thỏa mãn d[u]=min {d[z]:z∈T};T:=T\{u};(*cố định nhãn của đỉnh u*)For v∈T do (*gán nhãn lại cho csc đỉnh trong T*)If d[v]>d[u]+a[u,v] thenBegins đên v với mọi v∈S1 là đúng với bước lặp đầu tiên .Theo qui nạp là suy ra thuật toán cho ta đường đi ngắn nhất từ s đến mọi đỉnh của đồ thị .Bây giờ sẽ đánh giá số phép toán cần thực hiện theo thuật toán. Ở mỗi bước lặp để tìm ra điểm u cần thực hiện O(n) phép toán , để gán nhãn lại cũng cần thực hiện một số lượng phép toán cũng là O(n) .Thuật toán cần phải thực hiện n-1 bước lặp , vậy thời gian tính toán của thuật toán là cỡ O(n2).Định lý được chứng minh. Khi đã tìm được độ dài đường đi ngắn nhất d[v] thì đưòng đi này có thể tìm dựa vào nhãn Trước[v],v∈V.Thí dụ 1: Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị ở hìnhsau: (7) 32 6(5) (1)http://vuson.tk - Trang 13 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng ( 1 ) (2) (1) (1)(4) 1 (2) 4 (3) 5Kết quả tính toán theo thuật toán được trình bày trong bản dưới đây.Qui ước viết thành 2 phần của nhãn theo thứ tự : d[v], Truoc[v]. Đỉnh được đánh dấu * là đỉnh được chọn để cố định nhãn ở bước lặp đang xét , nhãn của nó không biến đổi ở cáccó chỉ số lớn hơn , nghĩa là mỗi cung của nó có thể biểu diễn dưới dạng (v[i],v[j]), trong đó i<j .T hí dụ 3. Đồ thị trong hình sau có các đỉnh được đánh số thỏa mãn điều kiện nêu trong định lý. 7 (3) 8 (5) t=9 (1) (1) s=1 (2) 4 (5) 5 (4)http://vuson.tk - Trang 14 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng 6(1) (7) (10)(5)2 (2) 3 Hình .Đồ thị không có chu trìnhĐể chứng minh định lý ta mô tả thuật toán sau, cho phép tìm ra cách đánh số thỏa mãn điều kiênk định lý.Procedure Numbering;(* Đầu vào : Đồ thị có hướng G=(V,E) với n đỉnh không chứa chu trình được cho bởi danh sách kề Ke(v),v∈ VĐầu ra: Với mỗi đỉnh v∈ V chỉ số NR[u] < NR[v]. *)BeginFor v∈ V do Vao[v]:=0;If Vao[v]=0 then QUEUE ⇐ v ; End; End;End;Thuật toán được xây dựng dựa trên ý tưởng rất đơn giản sau : Rõ rang trong đồ thịkhông có chu trình bao giờ cũng tìm được đỉnh có bán bậc vào bằng 0 ( không có cung đi vào ). Thực vậy, bắt đầu từ đỉnh v1 nếu có cung đi vào nó từ v2 thì ta lại chuyển sang xét đỉnh v2. Nếu có cung v3 đi vào v2, thì ta chuyển sang xét v3 Dođồ thị là không có chu trình nên sau một số hữu hạn lần chuyển như vậy ta phải điđến đỉnh không có cung đi vào . Thoạt tiên, tìm các đỉnh như vậy của đồ thị . Rõ ràng ta có thể đáng số chúng theo một thứ tự tuỳ ý bắt đầu từ 1.Tiếp theo, loại bỏ khỏi đồ thị những đỉnh đã được đánh số cùng các cung đi ra khỏi chúng, ta thu được đồ thị mới cũng không có chu trình, và thủ tục được lặp lại với đồ thị mới http://vuson.tk - Trang 15 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng này. Quá trình đó sẽ được tiếp tục cho đến khi tất cả các đinỉh của đồ thị được đánh số.Chú ý: 1) Rõ ràng trong bước khởi tạo ta phải duyệt qua tất cả các cung của đồ thịkhi tính bán bậc vào của các đỉnh, vì vậy ở đó ta tốn cỡ O(m) phép toán,trong đó m là số cung cua đồ thị . Tiếp theo mỗi lần đánh số một đỉnh, để thực hiện viêcv loại bỏ đỉnh đã được đánh số cùng với các cungđi ra khỏi nó , chúng ta sẽ phải duyệt qua tất cả các cung này. Suy ra để đánh số all các đỉnh củ đồ thị chúng ta sẽ phả duyệt tất cả các cung của đồ thị một lần nữa. Vậy độ phức tạp thuật toán la O(m).2) Thuật toán có thể để kiểm tra xem đồ thị có chứa chu trình hay không? Thực vậy, nếu kết thúc thuật toán vẫn còn có đỉnh chưa được đánh số PERT (Project Evaluation and Review Technique ) hqy CMD ( Critical path method)I.2.5 Đường đi ngắn nhất giữa tất cả các cặp đỉnhRõ ràng ta có thể giải bài toán tìm đường đi ngắn nhất giữa tất cả các căặpđỉnh củađồ thị bằng cách sử dụng n lần thuật toán mô tả ở mục trước, trong đó ta sẽ chọn shttp://vuson.tk - Trang 16 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng lần lượt là các đỉnh của đồ thị .Rõ ràng , khi đó ta thu được thuật toán với độ phức tạp là O(n4) (nếu dùng tt Ford-Bellman) hoặc O(n3) đối với trường hợp trọng số không âm hoặc đồ thị không có chu trình. Trong trường hợp tổng quát , sử dụng thuật toán Ford-Bellman n lần không phải là cách làm tốt nhất . Ở đây ta sẽ mô tả thuật toán với độ phức tạp tính toán O(n3) : thuật toán Floyd, tt được mô tả như sauProcedure Floyd;(* Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnhĐầu vào : Đồ thị cho bởi ma trận trọng số a[i,j], i,j=1,2, ,nĐầu ra : Ma trận đường đi ngắn nhất giữa các cặp đỉnhd[i,j] i,j =1,2, ,ntrong đó d[i,j] cho độ dài đường di ngắn nhất từ i đến j.Ma trận ghi nhận đường đip[i,j], i, j=1,2, ,n.trong đó p[i,j] ghi nhận đỉnh đi trước j trong đường đi ngắn nhất từi đến j.si nếu i kề s, d[j] =+ ∞ nếu j khôngkề s.II.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,w), với hàm trọng số w:E→ Rlà á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ốitiế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ểudiễ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) = ∑, 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à:http://vuson.tk - Trang 18 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng 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éttừ a đến v. Khởi tạo, dv = ∞, ∀v ∈ V \{a}, da = 0. 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à db là độ 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.II.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 trongij), a, zL(a) = 0L(v) = v aT(i) = 1 i n z TChọn v T sao cho L[v] đạt minT = T \ {v}x T & kề vL(x) = min(L(x), L(v) + c(v,x))EndSĐSĐ L(z)Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng II.3.4 Bảng dữ liệu chạy thô.Tạo ma trận như sau60 4 2 0 0 04 0 1 5 0 02 1 0 8 10 00 5 8 0 2 60 0 10 2 0 30 0 0 6 3 0 Ta có đồ thị như sau b 5 c Đề tài : Chương trình tìm đường đi ngắn nhất từ đỉnh S đến đỉnh T theo thuật toán Dijkstra _Sử dụng ngôn ngữ lập trình C#include<iostream.h>#include<conio.h>#include<stdlib.h>#include<stdio.h>#define m 50int C[m][m],DD[m],L[m],T[m];int n;void inmatran(char *st,int C[m][m]){ cout<<"\n\n"<<st; for(int i=1;i<=n;i++) { cout<<"\n"; for(int j=1;j<=n;j++) cout<<C[i][j]<<"\t"; }}void docfile(char *st){ FILE*f; int t; f=fopen(st,"rt"); if(f!=NULL){ fscanf(f,"%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) {DD[x]=v; } }}void duongdi(int a,int z){ cout<<"\n\n\tDo dai duong di ngan nhat : "<<L[z]; cout<<"\n\n\tDuong di: "; while(DD[z]!=0){ printf("%d < ",z); z=DD[z];} cout<<a;}void main(){ clrscr(); docfile("d:\\ok\\dacs\\matran.dnc"); //chú ý đường dẫn của ma trận cout<<"\n\n*** TIM minPath() BANG THUAT TOAN DIJKSTRA. ***";http://vuson.tk - Trang 24 -Website: http://www.docs.vn Email : [email protected] Tel : 0918.775.368Đồ án cơ sở GVHD: Đoàn Văn Thắng Dijkstra(a,z); // thay 1 giá trị cụ thể duongdi(a,z); // thay 1 giá trị cụ thể getch();}*****Kết luận******Tóm lại, thông qua môn học này giúp em nắm bắt tốt hơn về bài toán tìm đường đingắn nhất giữa hai đỉnh thông qua thuật toán Dijkstra.

Tải File Word Nhờ tải bản gốc Tài liệu, ebook tham khảo khác

• Thuật toán tìm đường đi ngắn nhất trong lý thuyết đồ thị
• Lý thuyết về thuật toán tìm đường đi ngắn nhất
• Tài liệu Đề tài
• nghiên cứu xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mở dạng khoảng
• đề tài CÀI đặt THUẬT TOÁN tìm ĐƯỜNG đi NGẮN NHẤT TRONG đồ THỊ
• đồ án cơ sở thuật toán tìm đường đi ngắn nhất trong lý thuyết đồ thị vuson.tk
• Báo cáo khoa học:
• Thuật toán tìm đường đi ngắn nhất và xây dựng ứng dụng ( Khóa luận tốt nghiệp )
• Một số thuật toán tìm đường đi ngắn nhất và xây dựng ứng dụng GAME PIKACHU
• Báo cáo khoa học tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất
• Những tư tưởng cơ bản của nho giáo và ảnh hưởng của nó ở nước ta
• Tiểu luận Sự biến động giá gạo trên thị trường Việt Nam và cách bình ổn giá
• Tiểu luận Xây dựng nhà nước pháp quyền XHCN Việt Nam hiện nay
• Tiểu luận Chọn và phân tích một số sự kiện tiêu biểu trong cuộc đời hoạt động cách mạng của Bác Hồ
• Tiểu luận Giá trị nhân văn trong tư tưởng Hồ Chí Minh
• So sánh Đào tạo luật ở Anh và đào tạo luật ở Việt Nam
• Đề cương môn tư tưởng Hồ Chí Minh
• Tìm hiểu giá trị nhân văn trong tư tưởng Hồ Chí Minh tại khu di tích lịch sử K9 – Đá Chông
• Tiểu luận Tư tưởng Hồ Chí Minh về mối quan hệ giữa dân tộc và giai cấp ở Việt Nam
• Tiểu luận Nguyên tắc xây dựng đạo đức mới theo tư tưởng Hồ Chí Minh

Hệ thống tự động tổng hợp link tải tài liệu, ebook miễn phí cho các bạn sinh viên tham khảo.

Học thêm

• Nhờ tải tài liệu
• Từ điển Nhật Việt online
• Từ điển Hàn Việt online
• Văn mẫu tuyển chọn
• Tài liệu Cao học
• Tài liệu tham khảo
• Truyện Tiếng Anh

Music ♫

Copyright: Tài liệu đại học ©

Top