BÀI 9
BÀI TOÁN ĐƯỜNG ĐI NGẮN
NHẤT TRÊN ĐỒ THỊ
1
Giáo viên: TS. Nguyễn Văn Hiệu
Email: nvhieuqt@dut.udn.vn
Nội dung
•Giới thiệu
•Bài toán
•Thuật toán Ford-Bellman
•Thuật toán Dijkstra
•Thuật toán Floyd
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
C B
A
E
D
F
0
3 2 8
5 8
4
8
7 1
2 5
2
3 9
Giới thiệu
Có nhiều cách đi giữa hai
điểm
Chọn ngắn nhất theo
nghĩa cự ly,
Chọn đường đi nhanh
nhất theo nghĩa thời gian
Chọn đường đi rẽ nhất
theo chi phí,
Chọn gửi dữ liệu nhanh
nhất.
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3
d(u,v)=?
mi j =1
mi j >0
G = (V , E)
Bài toán
Cho G = (V, E) là đồ thị
có trọng lượng.
s ∈ V và t ∈ V.
Hãy tìm đường đi có
tổng trọng lượng nhỏ
nhất từ s đến t.
•Đường đi ngắn nhất từ Etna đến
Oldtown là:
Etna – Bangor – Orono – OldTown
•Đường đi ngắn nhất từ Hermae
đến Etna là:
Hermae – Hampdea – Bangor - Etna
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
Bài toán
Điều kiện bài toán
Phải tồn tại đường đi từ s
đến t:
Đồ thị vô hướng liên thông
Đồ thị có hướng liên thông
mạnh
Đồ thị vô hướng, s và t nằm
trong cùng một thành phần
liên thông
Đồ thị có hướng, có tồn tại
đường đi từ s đến t
Trong đồ thị không tồn tại
chu trình âm
Đồ thị có hướng: không tồn
tại chu trình âm.
Đồ thị vô hướng: không tồn
tại cạnh âm.