


BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
& THUẬT TOÁN FLOYD-WARSHALL
ĐẠI HỌC ĐÀ NẴNG
GVHD: PGS. TSKH Trần Quốc Chiến
Nhóm học viên
•
Trần Ngọc Chinh
•
Phùng Thị Ngọc Dung
•
Trần Tấn Nha
•
Nguyễn Văn Phú
•
Võ Văn Thiên

 
!"#$%&'"()"*
"*+,
-,./".+,
Phát biểu bài toán

         
         
!   ! " # $  %& '
()*+,-./
+01!&234156!
  7  -89: ; < - = 75 > '

f7[g=:
Thuật toán
- Đầu vào:
hB)<5OP3QR9QPiY
Z:::j</=N%/3U9:
- Đầu ra:
kSlPm3U9n<3U9+b+
?2_U%/ -3U9:
kS`Pm-3U9n^)?2
(/ -":
Thuật toán(tt)

- Phương pháp:

120 Bước khởi tạo
34'"+&56*7"!8,
+9:$+;<=>?
+@$+;<=>9A;<=>B"CD";<=>($+;<=>9E∞B"
FGCD";<=>;.'B"FG@F"HID 
$+;<>9E∞>0
34'"-+&56*7"!8,
-+9:8+;<=>?
+@8+;<=>9=B"@"JB=(8+;<=>FG7,
KB"FG@"JB=0
,F9L0
∞
Thuật toán(tt)

1M0Kiểm tra kết thúcL
o!P!J:lPl+S+?2

5
a
Thuật toán(tt)
a b c d
a
+∞
7 5
+∞
b
+∞ +∞
7 6
c
+∞ +∞ +∞
11
d 4 1
+∞ +∞
a b c d
a b c
b c d
c d
d a b
u-.SFloyd-WarshallSGS=L
[MS^2-L
l
P
`P
S3a9
[
MSS-S#"L
3)G9

+∞ +∞ +∞
11
d 4 1 8 7
a b c d
a b c b
b c d
c d
d a b b b
M9
-M9
S3a9
[MSS-S#"L
a b c d
a 17 7 5 13
b 10 7 7 6
c 15 12 19 11
d 4 1 8 7
a b c d
a b b c b
b d d c d
c d d d d
d a b b b

9V9
-9-V9
S3a9
[MSS-S#"ML
a b c d
a
+∞


 !
" # $"%&'"()#%&"*+
,
-
 .
-
/
-
$'"(0'"(&0 1"*%&+
,
2
 .
2
/
2

,
#
 .
#
/
#
3 "*
"#45"*6"*%&'"(%&"*78
9(:;
 ,
#
  ,
#

g;:?:=?i;:?:F?E:F?:=?>>
 f
:?:=?9:?:F?E:F?:=?e
 -:?:=?9-:?:F?e
 j
 k&Ukf
:?:=?9:?:=?e
-:?:=?9-:?:=?e
 j
FEEe
 jA&k;Fh9>e
CÀI ĐẶT CHƯƠNG TRÌNH(tt)
•
3lD+5)
+U56792LLe
<5<Ae //n: so dinh, m: so cung, w:trong so
:567?:567?e//ma tran chua Do dai duong di
ngan nhat giua moi cap dinh
-:567?:567?e//ma tran chua duong di ngan nhat
giua moi cap dinh
CÀI ĐẶT CHƯƠNG TRÌNH(tt)
_m6$6"6+6W&+HZ6U6&&m_
%f7g=39
i
U!I
//Buoc khoi tao
~3PYI•PIpp9
~3UPYIU•PIUpp9
~3lmnmUnPPX9
lmnmUnP€€€I

4g73-`m-nmn9I
j
j