Chương 7: Bài toán tìm đường đi ngắn nhất
2
Chương 7 – Bài toán tìm đường đi ngắn nhất
Nội dung
Thuật toán Ford-Bellman
Giới thiệu
I.
II.
Thuật toán Dijkstra
III.
Thuật toán Floyd
IV.
Lý thuyết đồ thị
2
3
Chương 7 – Bài toán tìm đường đi ngắn nhất
I. Giới thiệu
Xét đồ thịcó hướng, có trọng sốG=(V, E)
⎩
⎨
⎧
∈
∉∞
=Evuifvua
Evuif
vungSoTro ),(),,(
),(,
),(
Với a(u, v) ∈R
Nếu dãy v0,v1,…,vp là 1 đường đi trên G
thì độ dài của nó được định nghĩa:
∑
=
−
=
p
i
iip vvavvvDoDai
1
110 ),(),...,,(
4
Chương 7 – Bài toán tìm đường đi ngắn nhất
I. Giới thiệu
Bài toán đường đi ngắn nhất
Giảsửcó nhiều đường đi từv0 đến vp: Đường đi
ngắn nhất là đường đi có tổng trọng sốcác cung nhỏ
nhất.
Đường đi từmột đỉnh
•Ford-Bellman
•Dijkstra
Đường đi từmột đỉnh
•Floyd
5
Chương 7 – Bài toán tìm đường đi ngắn nhất
Nội dung
Thuật toán Ford-Bellman
Giới thiệu
I.
II.
Thuật toán Dijkstra
III.
Thuật toán Floyd
IV.
Lý thuyết đồ thị
5