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)
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: