11B3-Nhóm 10-Tìm đường đi ngắn nhất trong đò thị vô hướng và có hướng


Từ: 21:49 13/10/2013
Bài: 8
Cảm ơn: 4
Thích: 1

BÁO CÁO CƠ BẢN CHUYÊN ĐỀ NGHÀNH

Nhóm 10:

Ứng dụng tìm kiếm đường đi, thông tin viễn thông giao thông vận tải,..(VD: google map…)

Viết chương trình mô phỏng .Cho một đường đi từ S--> Z như hình vẽ.Hãy tìm đường đi ngắn nhất từ S-->Z.(định luật Dijstra)

 

bai1

 

Bước 1: Gọi L1={S}  @(S)=0

Bước 2: Gọi L2={1,2}  @(1)=MIN{8}=8, @(2)=MIN{15}=15

Bước 3: Gọi L3={3}  @(3)=MIN{22,9,37}=9

Bước 4: Gọi L4={4,5}  @(4)=MIN{23,30}=23, @(5)=MIN{16,10,27}=10

Bước 5: Gọi L5={6}  @(6)=MIN{39,22,26}=20

Bước 6: Gọi L6={7,8}  @(7)=MIN{36,22}=22, @(8)=MIN{23,16,15}=15

Bước 7: Gọi L7={9}  @(9)=MIN{38,34,14,21}=14

Bước 8: Gọi L8={Z}  @(Z)=MIN{25,22,20}=20

Độ dài của đường đi ngắn nhất từ S-->Z=20

Cụ thể các điểm nó đi qua được chọn như sau.

Bắt đầu từ Z và lan tỏa ngược lại để tìm các đỉnh thuộc đường đi ngắn nhất.Đỉnh đó thuộc đường đi ngắn nhất với điều kiện:

 MIN(@x)+l(x,Z)=@Z    trong đó: x là tên đỉnh, l là chiều dài của đỉnh x đến Z

+ MIN(@9)+l(9,Z)=14+8=22 >20(loại)

+ MIN(@8)+l(8,Z)=15+5=20 =20(chọn)=> Z-->8

+ MIN(@7)+l(7,Z)=22+3=25 >20(loại)

+ MIN(@6)+l(6,8,Z)=20+3+5=28 >20(loại)

+ MIN(@5)+l(5,8,Z)=15+5=20 >20(chọn)=> Z-->8-->5

+ MIN(@4)+l(4,6,8,Z)=23+16+3=42 >20(loại)

+ MIN(@3)+l(3,8,Z)=9+7+5=21 >20(loại)

+ MIN(@2)+l(2,5,8,Z)=15+12+5+5=37 >20(loại)

+ MIN(@1)+l(1,3,8,Z)=8+14+7+5=34 >20(loại)

+ MIN(@S)+l(S,5,8,Z)=0+10+5+5=20 >20(chọn) => Z-->8-->5-->S

Vậy đường đi ngắn nhất sẽ là: S-->5-->8-->Z

Sau đây là demo minh họa bằng flash:

 

 

 

 

 

Label
Từ: 14:05 31/07/2013
Bài: 9
Cảm ơn: 6
Thích: 2

tớ là lớp 11b4. nhóm tớ chuyên đề ngành với bọn cậu. Bọn cậu mô phỏng thuật toán theo flash hay c#

Label
Từ: 21:49 13/10/2013
Bài: 8
Cảm ơn: 4
Thích: 1

Bọn tôi minh họa 1 bằng flash.còn thay thế các giá trị khác nhau của đồ thị như 1 đường đi khác thì dùng code c hoặc c++

 

Label
Từ: 14:05 31/07/2013
Bài: 9
Cảm ơn: 6
Thích: 2

nhóm tớ đang bảo làm bằng c# mà chúng nó kêu khó quá vì phải tự học hì...hì..Thầy Dũng lớp ấy nghiêm lắm à, lớp tớ thầy Hòa bảo lúc test có cả hội đồng mong là gặp người dễ =))

Label
Từ: 17:58 18/10/2013
Bài: 2
Cảm ơn: 2
Thích: 0

cái đồ thị ở trên có làm đơn giản đi được không Hà?(thay bằng đồ thị khác chẳng hạn)

Label
Từ: 21:49 13/10/2013
Bài: 8
Cảm ơn: 4
Thích: 1

cái minh họa thuật toán của 2 bài trên làm xong rồi..bây giờ ai biết có cách nào đưa flash lên forum không..nhóm mẫn quay màn hình rồi đăng lên youtube..nhóm mình làm thế nào..hay minh họa flash chỉ lên lớp trình diễn thôi...mọi người cho ý kiến

Label
Từ: 17:58 18/10/2013
Bài: 2
Cảm ơn: 2
Thích: 0

Tài biết cách đưa lên đó hỏi nó xem!!

Label
Từ: 10:39 21/09/2012
Bài: 33
Cảm ơn: 30
Thích: 10

Cách Upload Flash lên Forum đây nhé!

http://forum.fithou.net.vn/Trangcon.aspx?tid=2996&cid=121

Label
Từ: 21:49 13/10/2013
Bài: 8
Cảm ơn: 4
Thích: 1

không biết sao nhỉ..khi tớ đã úp file flash lên megaswf rồi.và nhận được dòng liên kết..khi tớ dán vào URL và sửa s thành flie rồi sao không được nhỉ

Label
Từ: 12:19 14/10/2013
Bài: 1
Cảm ơn: 0
Thích: 0

dongtaiit tớ không up dc plash theo như ông nói nhé

( phamdat_11b3)

Label
Từ: 10:39 21/09/2012
Bài: 33
Cảm ơn: 30
Thích: 10

@levietha2011, @manucian2906 các bạn xem lại thông tin mới Update trong bài viết xem được không nhé!

http://forum.fithou.net.vn/Trangcon.aspx?tid=2996&cid=121

Tin từ FITHOU

Khoa Công nghệ Thông tin - Viện ĐH Mở HN