3.3. Đường đi trong đồ thị
3.3.1. Định nghiã đường đi. 3.3.2. Tính liên thông. 3.3.3. Chu trình Euler và đường đi Euler. 3.3.4. Tìm đường đi ngắn nhất.
Oct 1, 2010 3.3. Đường đi trong đồ thị 1
3.3.4. Tìm đường đi ngắn nhất
Đồ thị có trọng số Định nghĩa 1.
Đồ thị vô hướng (có hướng) G =(V,E) được gọi là đồ thị có trọng số nếu mỗi cạnh (cung) e˛ E được đặt tương ứng với một số thực w(e). Số thực w(e) được gọi là trọng số của cạnh (cung) e.
Định nghĩa 2.
Ma trận trọng số của đơn đồ thị G =(V,E) là ma trận W=[wi,k]
trong đó
wi,k là trọng số của cạnh (cung) nối đỉnh thứ i với đỉnh thứ k
(nếu có);
nếu không có cạnh (cung) nối đỉnh thứ i với đỉnh thứ
wi,k=¥ k.
Oct 1, 2010 3.3. Đường đi trong đồ thị 2
3.3.4. Tìm đường đi ngắn nhất
Theo định nghiã trên:
các phần tử của ma trận trọng só có thể là các số âm. Một đơn đồ thị bất kỳ cũng có thể xem là đồ thị có trọng số nếu mỗi cạnh (cung) đều gắn trọng số là 1 (như định nghĩa đường đi độ dài 1 trong mục trước) và khi đó ma trận trọng số chính là ma trận 01.
Ví dụ:
xét một mạng hàng không, khi đó mạng này có thể coi là các
đồ thị có trọng số với các kiểu trọng số sau đây:
Độ dài cung đường bay Giá cước vận chuyển cho một đơn vị vận chuyển thời gian thực hiện chuyến bay giữa hai sân bay
Oct 1, 2010 3.3. Đường đi trong đồ thị 3
3.3.4. Tìm đường đi ngắn nhất
Ví dụ:
Ma trận trọng số của đồ thị trên là
=
W
0 15 20 0 20 14
15 0 11 18 0 24
20 11 0 13 22 0
0 18 13 0 16 21
20 0 22 16 0 12
14 24 0 21 12 0
ø Ø œ Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ Œ ß º
Oct 1, 2010 3.3. Đường đi trong đồ thị 4
3.3.4. Tìm đường đi ngắn nhất
Bài toán được đặt ra là:
tìm đường đi ngắn nhất trong đồ thị có trọng số G =(V,E) từ
đỉnh x đến đỉnh y cho trước.
Ý tưởng giải thuật là:
ta sẽ lần lượt duyệt và xác định độ dài của đường đi ngắn nhất từ đỉnh x đến các đỉnh lân cận, cho đến khi đỉnh đích y được duyệt.
Ở mỗi bước duyệt, mỗi đỉnh v sẽ được gắn nhãn, là cặp
(l(v);t(v)) trong đó:
l(v) là độ dài của đường đi tìm được từ đỉnh đầu x đến đỉnh v
cho đến thời điểm đang xét;
t(v) là đỉnh trước đỉnh v trong đường đi đó.
Oct 1, 2010 3.3. Đường đi trong đồ thị 5
3.3.4. Tìm đường đi ngắn nhất
Từ đó ta có thuật toán sau đây Dijkstra (Hà lan19302002):
V,
Bước khởi đầu: Với mọi đỉnh v ˛ l(v):= ¥
; {S là tập đỉnh đã được duyệt}
L(x):=0; {độ dài đường đi từ x đến x bằng 0} S:=˘ Bước lặp:
Khi yˇ S thực hiện:
; t(v):=‘’;
{u};
Tìm u trong tập các đỉnh chưa được duyệt (u˛ V\S) sao cho l(u) bé nhất; S:=S¨ Với mọi đỉnh v thuộc tập các đỉnh chưa được duyệt và có cạnh (cung) từ u đến
v, thực hiện
Nếu l(u) + wuv < l(v) thì
l(v):= l(u) + wuv ; t(v):=u;
Oct 1, 2010 3.3. Đường đi trong đồ thị 6
3.3.4. Tìm đường đi ngắn nhất
A3 ¥
A4 ¥
A6 ¥
Ví dụ: Tìm đường đi ngắn
Bước khởi đầu
nhất từ A1 đến A4
A1 0 0
A2 ¥ 15,A1 20,A1
A5 ¥ 20,A1 14, A1
0
15,A1 20,A1 35,A6 20,A1 14, A1
0
15,A1 20,A1 33,A2 20,A1 14, A1
0
15,A1 20,A1 33,A2 20,A1 14, A1
0
15,A1 20,A1 33,A2 20,A1 14, A1
0
15,A1 20,A1 33,A2 20,A1 14, A1
¥
Bước 1 A1 Bước 2 A6 Bước 3 A2 Bước 4 A3 Bước 5 A5 Bước 6 A4
Oct 1, 2010 3.3. Đường đi trong đồ thị 7
3.3.4. Tìm đường đi ngắn nhất
Giới thiệu chương trình
2
4
6
8
1
6
1
2
5 3 7
9
3
5
4
Oct 1, 2010 3.3. Đường đi trong đồ thị 8
3.3.4. Tìm đường đi ngắn nhất
Edsger Wybe Dijkstra
(sinh ngày 11 tháng 5, 1930 tại Rotterdam – mất ngày 6 tháng 8, 2002 tại Nuenen).
Là nhà khoa học máy tính Hà Lan. Ông được nhận giải thưởng Turing cho các đóng góp có tính chất nền tảng trong lĩnh vực ngôn ngữ lập trình.
Không lâu trước khi chết, ông đã được nhận giải Bài báo ảnh hưởng lớn trong lĩnh vực tính toán phân tán của ACM dành cho bài báo đã khởi đầu cho ngành con Self stabilization.
Sau khi ông qua đời, giải thưởng thường niên này đã được đổi tên thành giải thưởng ACM Edsger W. Dijkstra.
Edsger Dijkstra (ảnh của Brian Randell)
Oct 1, 2010 3.3. Đường đi trong đồ thị 9
