ĐƯỜNGĐINGẮNNHẤT
TRÊNĐỒTHỊ
CHƯƠNG5
TônQuangToại
KhoaCNTT,ĐạihọcNgoạingữ‐TinhọcTP.HCM
Cáckháiniệmmởđầu
Phátbiểubàitoán
ThuậttoánDijkstra
ThuậttoánFord–Bellman
ThuậttoánFloyd
Nộidung
Đồ thị có trọng số:Đồ thị G=(V,E)có trọng số
khi mỗi cạnh e=(u,v)của đồ thị được gán với
một consố w(u,v)và được gọi là trọng số của
cạnh e.
Đường đi:Đường đi giữa 2đỉnh svà tđược
cho bởi là dãy đỉnh
trong đó:

Cáckháiniệmmởđầu
Độ dài đường đi:Độ dài đường đi là tổng trọng
số của tất cả các cạnh trên đường đi đó
Cáckháiniệmmởđầu
𝑤𝑝𝑤󰇛𝑥
,𝑥󰇜


Vídụ:
p=(a,d,f,g)
w(p)=6+8+2=16
Phátbiểubàitoán
14
9
4
382
4
7
2
6
3
12
18
a
g
bc
d
ef