Cấu trúc dữ liệu và giải thuật (phần 20) pptx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (248.87 KB, 10 trang )
Đư
Đư
ờ
ờ
ng đi ng
ng đi ng
ắ
ắ
n nh
n nh
ấ
ấ
t
t
Giới thiệu:
Bài toán tìm đường đi ngắn nhất là bài
toán quan trọng trong lý thuyết đồ thi. Được ứng
dụng trong thực tế: Giao thông, viễn thông…
Bài toán chia làm 2 loại:
Tìm đường đi ngắn nhất giữa 1 cặp đỉnh: Cho 2
đỉnh u,v thuộc G, tìm đường đi ngắn nhất từ u đến
v : Dịkstra
Tìm đường đi ngắn nhất giữa tất cả các cặp
đỉnh: Tìm đường đi ngắn nhất từ đỉnh u đến đỉnh
v, với mọi cặp đỉnh u,v thuộc G: Floyd-Warshall
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t Dijkstra
t Dijkstra
Giới thiệu:
- Giải thuật Dijkstra giải bài toán đường đi ngắn
nhất nguồn đơn (Single Source Shortest Path) trên
một đồ thị có trọng số cạnh đều không âm.
- Xác định đường đi ngắn nhất giữa 2 đỉnh a,b cho trước
Đặt vấn đề:
Ứng dụng giải thuật cây bao trùm tối
thiểu để giải quyết bài toán đường đi ngắn nhất có
được không???
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t D
t D
ị
ị
kstra
kstra
Nhận xét:
- Giải thuật để giải bài toán MST sẽ không ứng dụng
được cho bài toán đường đi ngắn nhất.
- Vì sao??
- Vì vậy cần phải chỉnh sửa giải thuật trên để phù
hợp với bài toán đường đi ngắn nhất
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t D
t D
ị
ị
kstra
kstra
Giải thuật:
- Ở mỗi đỉnh v, giải thuật Dijkstra xác định 3 thông
tin: kv,dv,pv
• kv = 0 hoặc 1 – xác định trạng thái của đỉnh v ( 0 –
chưa chọn, 1 – đã chọn)
• dv: Chiều dài đường đi tìm thấy tại thời điểm đang
xét từ a đến v
• pv: là
đỉ
nh tr
ướ
c c
ủ
a
đỉ
nh v trên
đườ
ng
đ
i ng
ắ
n nh
ấ
t t
ừ
a
b
.
Đườ
ng
đ
i ng
ắ
n nh
ấ
t t
ừ a đế
n b có d
ạ
ng
{a,…,pv,v,…,b}
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t D
t D
ị
ị
kstra
kstra
B1: Khởi tạo: k
v
=0,∀v∈V; d
v
=
∞
,∀v ∈ V \{a}; d
a
=0.
B2: Chọn v∈V sao cho k
v
=0 và d
v
= min {d
t
/ t
∈
V,k
t
=0 }
– Nếu d
v
= ∞ thì kết thúc, không tồn tại đường đi từ a b.
B3: Đánh dấu đỉnh v, k
v
= 1.
B4: Nếu v=b thì kết thúc và d
b
là độ dài đường đi ngắn
nhất từ a b.
Ngược lại nếu v
≠
b sang B5.
B5: Với mỗi đỉnh u kề với v mà k
u
= 0, kiểm tra
Nếu d
u
> d
v
+ w(v,u) thì d
u
= d
v
+ w(v,u)
Ghi nhớ đỉnh v: p
u
:= v. Quay lại B2.
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t D
t D
ị
ị
kstra
kstra
Ví dụ:
Tìm đường đi ngắn
nhất từ A G
Shortest Tập hợp
A AB=2,AC=4.AD=7,AF=5
A,B
AB=2
AC=4.AD=7,AF=5,BE=3
,BG=8,BD=6
A,B,C
AB=2,AC=4
AD=7,AF=5,BE=3,BG=8
,
A,B,C,E
AB=2,AC=4,BE=3
AD=7,AF=5,BG=8
A,B,C,E,F
AB=2,AC=4,BE=3
BG=8,FD=1
A,B,C,E,F,D
AB=2,AC=4,BE=3,FD
=1
BG=8
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t D
t D
ị
ị
kstra
kstra
- Hình bên là cây đường đi ngắn nhất từ đỉnh A đến các
đỉnh
- Với ví dụ: AG, giải thuật sẽ kết thúc nếu tìm thấy
đỉnh G
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t D
t D
ị
ị
kstra
kstra
Tìm cây đường đi ngắn nhất từ đỉnh C đến các đỉnh
còn lại của đồ thị sau:
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t D
t D
ị
ị
kstra
kstra
Độ phức tạp của thuật toán:
- Bình thường thuật toán Dijkstra có độ phức tạp
O(n
2
+m).
- Nếu sử dụng cấu trúc heap O((n+m)*log2(n))
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t Floyd
t Floyd
-
-
Warshall
Warshall
Bài toán:
Tìm đường đi ngắn nhất của mỗi cặp đỉnh
trong đồ thị (All-Pairs Source Shortest Path)
