ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

ĐOÀN HOÀNG HẢI

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2015

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

ĐOÀN HOÀNG HẢI

CÁC THUẬT TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ: LÝ
THUYẾT, THUẬT TOÁN VÀ ỨNG DỤNG

Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số chuyên ngành: 60 48 0101

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC

GS-TS. ĐẶNG QUANG Á

Thái Nguyên - 2015

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

MỤC LỤC
LỜI NÓI ĐẦU ............................................................................................................1
Chƣơng I: MỘT SỐ KIẾN THỨC CƠ BẢN TRONG LÝ THUYẾT ĐỒ THỊ........2
1.1 Các khái niệm cơ bản của lý thuyết đồ thị .......................................................2
1.1.1 Định nghĩa đồ thị ........................................................................................2
1.1.2. Các thuật ngữ cơ bản .................................................................................5
1.1.3. Định nghĩa đường đi, chu trình, đồ thị liên thông. ....................................7
1.2 Đường đi ngắn nhất ........................................................................................11
1.2.1 Đường đi ngắn nhất xuất phát từ một đỉnh ...............................................11
1.2.2 Đường trong đồ thị không có chu trình ....................................................11
1.2.3 Đường đi ngắn nhất giữa hai cặp đỉnh ......................................................14
1.3 Một số bài toán dẫn đến bài toán tìm đường đi ngắn nhất trong đồ thị ..........15
1.3.1 Tìm đường đi ngắn nhất từ điểm A đến điểm B trong thành phố. ...........15
1.3.2 Tối ưu hệ thống mạng truyền dẫn. ............................................................18
Chƣơng II: ĐƢỜNG ĐI NGẮN NHẤT TỪ MỘT ĐỈNH ......................................21
2.1.Thuật toán Bellman-Ford ................................................................................27
2.2. Thuật toán Dijkstra .......................................................................................31
2.3. Thuật toán tìm kiếm A*. .................................................................................37
Chƣơng III : ĐƢỜNG ĐI NGẮN NHẤT GIỮA TẤT CẢ CÁC CẶP ĐỈNH ........40
3.1. Thuật toán Floyd-Warshall .............................................................................48
3.2. Thuật toán Johnson ........................................................................................55
Chƣơng IV: ỨNG DỤNG THUẬT TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT VÀO
MÔ HÌNH HỆ THỐNG ROUTING TĨNH ............................................................60

4.1. Nguyên lý hoạt động cơ bản của Router trong hệ thống mạng. .....................60
4.2. Ứng dụng một thuật toán (Dijkstra). ..............................................................69
4.3. Thiết kế chương trình áp dụng thuật toán (Floyd-Warshall). .........................71
4.4. Kết quả thử nghiệm ........................................................................................71
TÀI LIỆU THAM KHẢO ........................................................................................73

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

1

LỜI NÓI ĐẦU
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đời và có nhiều ứng
dụng hiện đại.Những tư tưởng cơ bản của lý thuyết đồ thị đươc đề xuất từ những
năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler.
Đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau.
Chẳng hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích
mạch điện. Chúng ta có thể phân biệt các hợp chất hoá học hữu cơ khác nhau với
cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta
có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin được với
nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các
cạnh có thể sử dụng để giải các bài toán như : tìm đường đi ngắn nhất giữa hai
thành phố trong cùng một mạng giao thông. Chúng ta còn sử dụng đồ thị để giải các
bài toán về lập lịch, thời khoá biểu và phân bố tần số cho các trạm phát thanh và
truyền hình.
Trong đời sống, chúng ta thường gặp các tình huống như sau: để đi từ điểm A
đến điểm B trong thành phố, có nhiều đường đi, nhiều cách đi; có lúc ta chọn đường
đi ngắn nhất (theo nghĩa cự ly), có lúc lại cần trọn đường đi nhanh nhất (theo nghĩa
thời gian),v.v…

Mục đích đề tài tìm hiểu, nghiên cứu các thuật toán tìm đường đi ngắn nhất
trong đồ thị phục vụ việc nghiên cứu khoa học và ứng dụng vào thực tiễn.
Củng cố và rèn luyện kỹ năng lập trình, nhớ lại các thuật toán
Chƣơng I

: Một số kiến thức cơ bản trong lý thuyết đồ thị.

Chƣơng II

: Đường đi ngắn nhất từ một đỉnh.

Chƣơng III

: Đường đi ngắn nhất giữa tất cả các cặp đỉnh.

Chƣơng IV

: Ứng dụng thuật toán tìm đường đi ngắn nhất vào mô hình
hệ thống routing tĩnh.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

2

Chƣơng I: MỘT SỐ KIẾN THỨC CƠ BẢN TRONG LÝ
THUYẾT ĐỒ THỊ
1.1 Các khái niệm cơ bản của lý thuyết đồ thị
1.1.1 Định nghĩa đồ thị

Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này.
Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh
nào đó của đồ thị. Để có thể hình dung được tại sao lại cần đến các loại đồ thị khác
nhau, chúng ta sẽ nêu ví dụ sử dụng chúng để mô tả mạng máy tính. Giả sử ta có
một mạng gồm các máy tính và kênh điện thoại (gọi tắt là tên thoại) nối các máy
tính này. Chúng ta có thể biểu diễn các vị trí đặt máy tính bởi các điểm và các kênh
thoại nối chúng bởi các đoạn nối, xem hình 1.1
Hà Tây

Đồng Nai
Huế

Hà Nội

An Giang

Bình Định

TPHCM

Quãng Ngãi
Phú Yên

Khánh Hòa

Hình 1.1 Sơ đồ mạng máy tính
Nhận thấy rằng trong mạng hình 1, giữa hai máy tính bất kỳ chỉ cho phép nhiều
nhất là một kênh thoại nối chúng, kênh thoại này cho phép liên lạc cả hai chiều và
không có máy tính nào lại được nối với chính nó. Sơ đồ mạng máy tính cho trong
hình 1 được gọi là đơn đồ thị vô hướng ta đi đến định nghĩa sau:

Định nghĩa 1. Đơn đồ thị vô hướng G=(V,E) bao gồm V là tập đỉnh và E là tập các
cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.
Trong trường hợp giữa hai máy tính nào đó thường xuyên phải truyền tải nhiều
thông tin người ta phải nối hai máy này bởi nhiều kênh thoại. Mạng với đa kênh
thoại giữa các máy tính được cho trong hình 1.2

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

3

Đồng Nai

Hà Tây

An Giang

Huế

Hà Nội

Bình Định

TPHCM

Khánh Hòa

Quảng Ngãi
Phú Yên


Hình 1.2 Sơ đồ mạng máy tính với đa kênh thoại
Định nghĩa 2. Đa đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh, và E là họ
các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh .Hai
cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh.
Đồng Nai

Hà Tây

An Giang

Huế

Hà Nội

Bình Định

TPHCM

Khánh Hòa

Quảng Ngãi
Phú Yên

Hình 1.3 Sơ đồ mạng máy tính với kênh thông báo.
Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị nào cũng là
đơn đồ thị, vì trong đa đồ thị có hai hay nhiều hơn cạnh nối một cặp đỉnh nào đó.
Trong mạng máy tính có thể có những kênh thoại nối một máy tính nào đó với
chính nó. Mạng như vậy được cho trong hình 1.3. Như vậy đa đồ thị không thể mô


Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

4

tả được mạng như vậy, bởi vì có những khuyên (cạnh nối một đỉnh vói chính nó).
Trong trường hợp này chúng ta cần sử dụng đến khái niệm giả đồ thị vô hướng,
được định nghĩa như sau:
Định nghĩa 3. Giả đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh, và E là họ
các cặp không có thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V
gọi là các cạnh. Cạnh e được gọi là khuyến nếu có dạng e=(u,u).
Các kênh thoại trong mạng máy tính có thể chỉ cho phép truyền tin theo một chiều.
Chẳng hạn trong hình 1.4 máy chủ ở Hà Nội chỉ có thể nhận tin từ các máy ở địa
phương, có một số máy chỉ có thể gửi tin đi, còn các kênh thoại cho phép truyền tin
theo cả hai chiều được thay thế bởi hai cạnh có hướng ngược chiều nhau.
Hà Tây

Đồng Nai

Hà Nội

Huế

An Giang

TPHCM

Phú Yên


Bình Định

Khánh Hòa
Hình 1.4 Mạng máy tính với các kênh thoại một chiều

Định nghĩa 4. Đơn đồ thị có hướng G=(V,E) bao gồm V là tập các đỉnh, và E là tập
các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung.
Nếu trong mạng có thể có đa kênh thoại một chiều, ta sẽ phải sử dụng đến khái
niệm đa đồ thị có hướng:
Định nghĩa 5. Đa đồ thị có hướng G=(V,E) bao gồm V là tập các đỉnh,và E là họ
các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e1 và
e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp.
Trong các phần tiếp theo chủ yếu chúng ta sẽ làm việc với đơn đồ thị vô hướng và
đơn đồ thị có hướng. Vì vậy, để cho ngắn gọn, ta sẽ bỏ qua tính từ đơn mỗi khi nhắc
đến chúng.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

5

1.1.2. Các thuật ngữ cơ bản
Trong mục này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ
thị. Trước tiên, ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hướng.
Định nghĩa 1. Hai đỉnh u và v của đồ thị có hướng G được gọi là kề nhau nếu (u,v)
là cạnh của đồ thị G. Nếu e=(u,v) là cạnh của đồ thị thì ta nói cạnh này là cạnh liên
thuộc với hai đỉnh u và v, hoặc cũng nói là cạnh e nối đỉnh u và đỉnh v, đồng thời
các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u,v).
Để có thể biết có bao nhiêu cạnh liên thuộc với một đỉnh, ta đưa vào định nghĩa sau

Định nghĩa 2. Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc
với nó ta sẽ kí hiệu là deg(v).
b

a

c

f

e

d

g

Hình 1.5 Đồ thị vô hướng
Thí dụ. Xét đồ thị cho trong hình 1.5, ta có
deg(a)=1, deg(b)=4 , deg(c)=4 , deg(f)=3, deg(d)=1 ,
deg(e)=3 , deg(g)=0.
Đỉnh bậc 0 gọi là đỉnh cô lập, đỉnh bậc 1 được gọi là đỉnh treo. Trong ví dụ trên
đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau :
Định lý 1. Giả sử G=(V,E) là đồ thị vô hướng với m cạnh. Khi đó
2m=  deg(v)
vV

Chứng minh. Rõ ràng trong mỗi cạnh e=(u,v) được tính một lần trong deg(u) và
một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số
cạnh
Thí dụ 2. Đồ thị với n đỉnh và mỗi đỉnh có bậc là 6 có bao nhiêu cạnh ?

Giải: Theo định lý 1, ta có 2m=6n. Từ đó suy ra số cạnh của đồ thị là 3n.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

6

Hệ quả. Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số
chẵn.
Chứng minh. Thực vậy, gọi O và U tương ứng là tập đỉnh bậc lẻ và tập đỉnh bậc
chẵn của đồ thị,ta có
2m=  deg(v) +  deg(v) +  deg(v)
vV

vO

vU

Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ hai trong vế phải ở trên là số
chẵn. Từ đó suy ra tổng thứ nhất (chính là tổng bậc của các đỉnh bậc lẻ) cũng phải là
số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn
các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn.
Ta xét các thuật ngữ tương tự cho đồ thị có hướng.
Định nghĩa 3. Nếu e=(u,v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v
là kề nhau, và nói cung(u,v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra
khỏi đỉnh u và đi vào đỉnh v. Đinh u (v) sẽ được gọi là đỉnh đầu (cuối) của cung
(u,v).
Tương tự như khái niệm bậc, đối với đồ thị có hướng ta có khái niệm bán bậc ra
(vào) của một đỉnh.

Định nghĩa 4. Ta gọi bán bậc ra (vào) của đỉnh v trong đồ thị có hướng là số cung
của đồ thị đi ra khỏi nó (đi vào nó) và kí hiệu là deg+(v)(deg-(v)).
a

e

b

c

d
Hình 1.6 Đồ thị có hướng G

Thí dụ 3. Xét đồ thị cho trong hình 1.6 Ta có
deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e)=2.
deg+(a)=3, deg+(b)=1 deg+(c)=1, deg+(d)=2, deg+(e)=2
Do mỗi cung (u,v) sẽ được tính một lần trong bán bậc vào của đỉnh v và một
lần trong bán bậc ra của đỉnh u nên ta có

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

7

Định lý 2. Giả sử G=(V,E) là đồ thị có hướng, khi đó

 deg




vV

(v)   deg  (v) | E |
vV

Rất nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng trên các cung
của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn nếu ta bỏ qua hướng trên
các cung của đồ thị. Đồ thị vô hướng thu được bằng cách bỏ qua hướng trên các
cung được gọi là đồ thị vô hướng tương ứng với đồ thị có hướng đã cho.
1.1.3. Định nghĩa đƣờng đi, chu trình, đồ thị liên thông.
Định nghĩa 1. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên
dương, trên đồ thị vô hướng G=(V,E) là dãy
xo, x1 , ... , xn-1 , xn
trong đó u= xo , v= xn , (xi , xi+1) ∈ E , i=0,1,2,...,n-1.
Đường đi nói trên còn có thể biểu diễn dưới dạng các cạnh:
(xo, x1) , (xo, x2), ... , (xn-1 , xn).
Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh
đầu trùng với đỉnh cuối (tức là u=v) được gọi là chu trình. Đường đi hay chu trình
được gọi là đơn nếu như không có cạnh nào bị lặp lại.
Thí dụ 1. Trên đồ thị vô hướng cho trong hình 1.7: a,d,c,f,e là đường đi đơn độ dài
4. Còn d,e,c,a không là đường đi do (e,c) không phải là cạnh của đồ thị. Dãy
b,c,f,e,b là chu trình độ dài 4. Đường đi a,b,e,d,a,b có độ dài là 5 không phải là
đường đi đơn, do cạnh (a,b) có mặt trong nó hai lần.

a

d

b


e

c a

b

f d
e
Hình 1.7 Đường đi trên đồ thị

Số hóa bởi Trung tâm Học liệu - ĐHTN

c

f

/>

8

Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa hoàn toàn
tương tự như trường hợp đồ thị vô hướng, chỉ khác là ta chú ý đến hướng trên các
cung.
Định nghĩa 2. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên
dương, trên đồ thị có hướng G=(V,A) là dãy
𝑥0 , 𝑥1 , ... , 𝑥𝑛 −1 , 𝑥𝑛
trong đó u=𝑥0 , v=𝑥𝑛 , (𝑥𝑖 , 𝑥𝑖+1 ) ∈ A , i= 0, 1, 2 ,..., n-1.
Đường đi nói trên còn có thể biểu diễn dưới dạng các cung:
(𝑥0 , 𝑥1 ) , 𝑥0 , 𝑥2 ), ... , (𝑥𝑛 −1 , 𝑥𝑛 ).

Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh
đầu trùng với đỉnh cuối (tức là u=v) được gọi là chu trình. Đường đi hay chu trình
được gọi là đơn nếu như không có cung nào bị lặp lại.
Thí dụ 2. Trên đồ thị có hướng cho trong hình 1: a⟶d⟶c⟶f⟶e là đường đi đơn
độ dài 4. Còn d⟶e⟶c⟶a không là đường đi do (e,c) không phải là cung của đồ
thị. Dãy b,c,f,e,b là chu trình độ dài 4. Đường đi a⟶b⟶e⟶d⟶a⟶b có độ dài là
5 không phải là đường đi đơn, do cung (a,b) có mặt trong nó hai lần.
Xét một mạng máy tính. Một câu hỏi đặt ra là hai máy tính bất kỳ trong mạng
này có thể trao đổi được thông tin với nhau hoặc trực tiếp qua kênh nối chúng hoặc
thông qua một hoặc vài máy tính trung gian trong mạng ? Nếu sử dụng đồ thị để
biểu diễn mạng máy tính này (trong đó các đỉnh của đồ thị tương ứng với các máy
tính, còn các cạnh tương ứng với các kênh nối) câu hỏi đó được phát biểu trong
ngôn ngữ đồ thị như sau: Tồn tại hay chăng đường đi giữa mọi cặp đỉnh của đồ thị ?
Định nghĩa 3. Đồ thị vô hướng G=(V,E) được gọi là liên thông nếu luôn tìm được
đường đi giữa hai đỉnh bất kỳ của nó.
Như vậy hai máy tính bất kỳ trong mạng có thể trao đổi thông tin được với nhau khi
và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thông.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

9

Thí dụ 3. Trong hình 1.8: Đồ thị G là liên thông, đồ thị H là không liên thông
a

b
H1
c

d

e
H2

g

f
(G)

H3
(H)

Hình 1.8 Đồ thị liên thông G và đồ thị H gồm 3 thành phần liên thông H1,H2,H3.
Định nghĩa 4. Ta gọi đồ thị con của đồ thị G=(V,E) là đồ thị H=(W,F), trong đó
W ⊆ V và F ⊆ E
Trong trường hợp đồ thị là không liên thông, nó sẽ rã ra thành một số đồ thị con
liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ
gọi là các thành phần liên thông của đồ thị.
Thí dụ 4. Đồ thị H trong hình 1.8 gồm 3 thành phần liên thông là H1,H2,H3.
Trong mạng máy tính có thể có những máy (những kênh nối) mà sự hỏng hóc của
nó có thể ảnh hưởng đến việc trao đổi thông tin trong mạng. Các khái niệm tương
ứng với tình huống này được đưa ra trong định nghĩa sau.
Định nghĩa 5. Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các
cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị.
Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên
thông của đồ thị .
Thí dụ 5. Trong đồ thị G ở hình 2, đỉnh d và e là đỉnh rẽ nhánh, còn các cạnh (d,g)
và (e,f) là cầu.
Đối với đồ thị có hướng có hai khái niệm liên thông phụ thuộc vào việc ta có

xét đến hướng trên các cung hay không.
Định nghĩa 6. Đồ thị có hướng G=(V,A) được gọi là liên thông mạnh nếu luôn tìm
được đường đi giữa hai đỉnh bất kỳ của nó.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

10

Định nghĩa 7. Đồ thị có hướng G=(V,A) được gọi là liên thông yếu nếu đồ thị vô
hướng tương ứng với nó là đồ thị vô hướng liên thông.
Rõ ràng nếu đồ thị là liên thông mạnh thì nó cũng là liên thông yếu, nhưng điều
ngược lại là không luôn đúng, như chỉ ra trong thí dụ dưới đây.
Thí dụ 6. Trong hình 1.9 đồ thị G là liên thông mạnh, còn H là liên thông yếu
nhưng không là liên thông mạnh
a

b
a

b

e
e
c

d
c
(G)


d
(H)

Hình 1.9 Đồ thị liên thông mạnh G và đồ thị liên thông yếu H
Một câu hỏi đặt ra là khi nào có thể định hướng các cạnh của một đồ thị vô hướng
liên thông để có thể thu được một đồ thị có hướng liên thông mạnh? Ta sẽ gọi đồ thị
như vậy là đồ thị định hướng được. Định lý dưới đây cho ta tiêu chuẩn nhận biết
một đồ thị có là định hướng được hay không.
Định lý 1. Đồ thị vô hướng liên thông là định hướng được khi và chỉ khi mỗi cạnh
của nó nằm trên ít nhất một chu trình.
Chứng minh. Điều kiện cần. Giả sử (u,v) là một cạnh của đồ thị, từ sự tồn tại
đường đi có hướng từ u đến v và ngược lại suy ra (u,v) phải nằm trên ít nhất một
chu trình.
Điều kiện đủ. Thủ tục sau đây cho phép định hướng các cạnh của đồ thị để thu
được đồ thị có hướng liên thông mạnh. Giả sử C là một chu trình nào đó trong đồ
thị. Định hướng các cạnh trên chu trình này theo một hướng đi vòng theo nó. Nếu
tất các cạnh của đồ thị là đã được định hướng thì kết thúc thủ tục. Ngược lại, chọn C
là một cạnh chưa định hướng có chung đỉnh với ít nhất một trong số các cạnh đã
định hướng. Theo giả thiết tìm được chu trình C chứa cạnh e. Định hướng các cạnh

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

11

chưa được định hướng của C’ theo một hướng dọc theo chu trình này (không định
hướng lại các cạnh đã có hướng). Thủ tục trên sẽ được lặp lại cho đến khi tất cả các
cạnh của đồ thị được định hướng. Khi đó ta thu được đồ thị có hướng liên thông

mạnh
1.2 Đƣờng đi ngắn nhất
1.2.1 Đƣờng đi ngắn nhất xuất phát từ một đỉnh
Phần lớn các thuật toán tìm khoảng cách giữa hai đỉnh s và t được xây dựng
nhờ kỹ thuật tính toán mà ta có thể mô tả như sau: từ ma trận trọng số a[u,v],u,v V,
ta tính cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v V. Mỗi khi phát
hiện
d[u]+a[u,v]
(1)

cận trên d[v] sẽ được tốt lên : d[v]=d[u]+a[u,v].
Quá trình đó sẽ kết thúc khi nào chúng ta không làm tốt thêm được bất cứ cận
trên nào. Khi đó, rõ ràng giá trị của mỗi d[v] sẽ cho ta khoảng cách từ mỗi đỉnh s
đến v. Khi thể hiện kỹ thuật tính toán này trên máy tính, cận trên d[v] sẽ được gọi là
nhãn của đỉnh v, còn việc tính lại các cận trên này sẽ gọi là phép gán nhãn cho đồ
thị và toàn bộ thủ tục thường gọi là thủ tục gán nhãn.
Sơ đồ tính toán mà ta vừa mô tả còn chưa là xác định, bởi vì còn phải chỉ ra
thứ tự chọn các đỉnh u và v để kiểm tra điều kiện (1). Thứ tự chọn này có ảnh
hưởng rất lớn đến hiệu quả thuật toán.
1.2.2 Đƣờng trong đồ thị không có chu trình
Bây giờ ta xét trường hợp riêng thứ hai của bài toán tìm đường đi ngắn nhất,
mà để giải nó có thể xây dựng thuật toán với độ phức tạp tính toán O(𝑛2 ), đó là đồ
thị không có chu trình (còn trọng số trên các cung có thể là các số thực tuỳ ý).
Trước hết ta chứng minh định lý sau
Định lý 2. Giả sử G là đồ thị không có chu trình. Khi đó các đỉnh của nó có thể
đánh số sao cho mỗi cung của đồ thị chỉ hướng từ đỉnh có chỉ số nhỏ hơn đến đỉnh

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

12

có chỉ số lớn hơn, nghĩa là mỗi cung của nó có thể biểu diễn dưới dạng (v[i],v[j]),
trong đó iThí dụ 3. Đồ thị trong hình 1.10 có các đỉnh được đánh số thỏa mãn điều kiện nêu
trong định lý.
7

(3)

8
(5)

(1)
s=1

t=9

(1)
(2)

(1)

4

(5)
(7)

5

(4)
6

(10)
(5)

2 (2)
3
Hình 1.10 Đồ thị không có chu trình
Để chứng minh định lý ta mô tả thuật toán sau, cho phép tìm ra cách đánh số thỏa
mãn điều kiện định lý.
Procedure Numbering;
(*
Đầu vào: Đồ thị có hướng G=(V,E) với n đỉnh không chứa chu trình được
cho bởi danh sách kề Ke(v),v  V
Đầu ra: Với mỗi đỉnh v  V chỉ số NR[u] < NR[v]. *)
Begin
For v  V do Vao[v]:=0;
(* tinh Vao[v]=deg-(v) *)
For u  V do
For v  Ke(u) do Vao[v]:=Vao[v] + 1;
QUEUE:=  ;
For v  V do
If Vao[v]=0 then QUEUE  v ;
Num :=0;
While QUEUE   do
Begin u  QUEUE;
Num :=num +1; NR[u] :=num;

For v  Ke(u) do
Begin
Vao[v]:=Vao[v] - 1;
If Vao[v]=0 then QUEUE  v ;
End;
End;
End;
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

13

Thuật toán được xây dựng dựa trên ý tưởng rất đơn giản sau: Rõ ràng trong
đồ thị không có chu trình bao giờ cũng tìm được đỉnh có bán bậc vào bằng 0 (không
có cung đi vào). Thực vậy, bắt đầu từ đỉnh v1 nếu có cung đi vào nó từ v2 thì ta lại
chuyển sang xét đỉnh v2. Nếu có cung v3 đi vào v2, thì ta chuyển sang xét v3... Do
đồ thị là không có chu trình nên sau một số hữu hạn lần chuyển như vậy ta phải đi
đến đỉnh không có cung đi vào. Đầu tiên, tìm các đỉnh như vậy của đồ thị. Rõ ràng
ta có thể đánh số chúng theo một thứ tự tuỳ ý bắt đầu từ 1. Tiếp theo, loại bỏ khỏi
đồ thị những đỉnh đã được đánh số cùng các cung đi ra khỏi chúng, ta thu được đồ
thị mới cũng không có chu trình, và thủ tục được lặp lại với đồ thị mới này. Quá
trình đó sẽ được tiếp tục cho đến khi tất cả các đỉnh của đồ thị được đánh số.
Chú ý:
1. Rõ ràng trong bước khởi tạo ta phải duyệt qua tất cả các cung của đồ thị khi
tính bán bậc vào của các đỉnh, vì vậy ở đó ta tốn cỡ O(m) phép toán, trong đó
m là số cung của đồ thị. Tiếp theo mỗi lần đánh số một đỉnh, để thực hiện
việc loại bỏ đỉnh đã được đánh số cùng với các cung đi ra khỏi nó, chúng ta
sẽ phải duyệt qua tất cả các cung này. Suy ra để đánh số tất cả các đỉnh của
đồ thị chúng ta sẽ phải duyệt tất cả các cung của đồ thị một lần nữa. Vậy độ

phức tạp thuật toán là O(m).
2. Thuật toán có thể để kiểm tra xem đồ thị có chứa chu trình hay không? Thực
vậy, nếu kết thúc thuật toán vẫn còn có đỉnh chưa được đánh số (numđiều đó có nghĩa là đồ thị chứa chu trình.
Do có thuật toán đánh số trên, nên khi xét đồ thị không có chu trình ta có thể giả
thiết là các đỉnh của nó được đánh số sao cho mỗi cung chỉ đi từ đỉnh có chỉ số nhỏ
đến đỉnh có chỉ số lớn hơn. Thuật toán tìm đường đi ngắn nhất trên đồ thị không có
chu trình được mô tả trong sơ đồ sau đây:
Procedure Critical_Path;
(* Tìm đƣờng đi ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh còn lại trên đồ
thị không có chu trình *)
Đầu vào: Đồ thị G=(V,E) trong đó V= { v[1], v[2], ..., v[n] }
Đối với mỗi cung (v[i],v[j])  E ta có iSố hóa bởi Trung tâm Học liệu - ĐHTN

/>

14

Đồ thị được cho bởi danh sách kề Ke(v),v  V.
Đầu ra: Khoảng cách từ v[1] đến tất cả các đỉnh còn lại được ghi trong
mảng d[v[i] ], i=1,2,...,n * )
Begin
d[v[1] ]:=0;
for j:=2 to n do d[v[j] ]:=a[v[1] ],v[j] ];
fo j:=2 to n do
for v  Ke [v [j ] ] do
d [v ]:=min ( d [v ], d [v [j ] ] + a [v [j ] ], v );
end;
Độ phức tạp của thuật toán là O(m), do mỗi cung của đồ thị phải xét qua

đúng một lần.
Các thuật toán mô tả ở trên thường được ứng dụng vào việc xây dựng những
phương pháp giải bài toán điều khiển việc thực hiện những dự án lớn, gọi tắt là
PERT (Project Evaluation and Review Technique) hay CMD ( Critical path
method)
1.2.3 Đƣờng đi ngắn nhất giữa hai cặp đỉnh
Rõ ràng ta có thể giải bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh
của đồ thị bằng cách sử dụng n lần thuật toán mô tả ở mục trước, trong đó ta sẽ
chọn s lần lượt là các đỉnh của đồ thị. Rõ ràng, khi đó ta thu được thuật toán với độ
phức tạp là O(n4) (nếu dùng thuật toán Ford-Bellman) hoặc O(n3) đối với trường
hợp trọng số không âm hoặc đồ thị không có chu trình. Trong trường hợp tổng quát,
sử dụng thuật toán Ford-Bellman n lần không phải là cách làm tốt nhất. Ở đây ta sẽ
mô tả thuật toán với độ phức tạp tính toán O(n3) : thuật toán Floyd, thuật toán được
mô tả như sau:
Procedure Floyd;
(* Tìm đƣờng đi ngắn nhất giữa tất cả các cặp đỉnh
Đầu vào: Đồ thị cho bởi ma trận trọng số a[i,j], i,j=1,2,...,n
Đầu ra: Ma trận đường đi ngắn nhất giữa các cặp đỉnh
d[i,j] i,j =1,2,...,n
trong đó d[i,j] cho độ dài đường di ngắn nhất từ i đến j.
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

15

Ma trận ghi nhận đường đi
p[i,j], i, j=1,2,...,n.
trong đó p[i,j] ghi nhận đỉnh đi trước j trong đường đi ngắn nhất từ i
đến j.

*)
Begin (* Khởi tạo *)
For i:=1 to n do
For j:=1 to n do
Begin
d[i,j]:=a[i,j];
p[i,j]:=i;
end;(* Bước lặp *)
For k:=1 to n do
For i:=1 to n do
For j:=1 to n do
If d[i,j] > d[i,k] + d[k,j] then
Begin
d[i,j]:= d[i,k] + d[k,j ];
p [i,j ]:= p [k,j ];
end;
end;
Rõ ràng độ phức tạp của thuật toán là O(n3).
1.3 Một số bài toán dẫn đến bài toán tìm đƣờng đi ngắn nhất trong đồ thị
1.3.1 Tìm đƣờng đi ngắn nhất từ điểm A đến điểm B trong thành phố.
Trong đời sống, chúng ta thường gặp những tình huống như sau: để đi từ địa
điểm A đến địa điểm B trong thành phố, có nhiều đường đi, nhiều cách đi; có lúc ta
chọn đường đi ngắn nhất (theo nghĩa cự ly), có lúc lại cần chọn đường đi nhanh
nhất (theo nghĩa thời gian) và có lúc phải cân nhắc để chọn đường đi rẻ tiền nhất
(theo nghĩa chi phí), v.v...
Có thể coi sơ đồ của đường đi từ A đến B trong thành phố là một đồ thị, với
đỉnh là các giao lộ (A và B coi như giao lộ), cạnh là đoạn đường nối hai giao lộ.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

16

Trên mỗi cạnh của đồ thị này, ta gán một số dương, ứng với chiều dài của đoạn
đường, thời gian đi đoạn đường hoặc cước phí vận chuyển trên đoạn đường đó, ...
Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh (hoặc cung) được gán một
giá trị (nguyên hoặc thực) gọi là trọng số ứng với cạnh (hoặc cung) đó.
Có thể xem một đồ thị G bất kỳ là một đồ thị có trọng số mà mọi cạnh đều có
chiều dài 1. Khi đó, khoảng cách d(u,v) giữa hai đỉnh u và v là chiều dài của đường
đi từ u đến v ngắn nhất, tức là đường đi qua ít cạnh nhất.
Bài toán tìm đƣờng đi ngắn nhất
Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách d(s,f) từ một
đỉnh s cho trước đến một đỉnh f bất kỳ của G và tìm đường đi ngắn nhất từ s đến f.
Nếu như đồ thị có chu trình âm (chu trình với độ dài âm) thì khoảng cách giữa
một số cặp đỉnh nào đó có thể không xác định. Trong trường hợp này có thể tìm
đường đi cơ bản ngắn nhất.
Nếu như đồ thị không có chu trình âm thì ta có thể chứng minh được rằng một
trong những đường đi ngắn nhất là đường đi cơ bản. Việc tìm đường đi ngắn nhất
giữa 2 đỉnh s và f có thể áp dụng thuật toán sau:
Gọi a[u,v] là trọng số của cạnh (u,v). Qui ước a[v,v]=0 với ∀vV Đặt d[s,v] là
khoảng cánh từ s tới v. Để tìm đường đi từ s tới f ta nhận thấy rằng luôn tồn tại f1≠ f
sao cho d[s,f]=d[s,f1]+a[f1,f].
Đỉnh f1 đó là đỉnh liền trước trong đường đi từ s tới f. Nếu f1≡ s thì kết thúc
trái lại ta tìm đỉnh f2 sao cho d[s,f1]=d[s,f2]+a[f2,f]. Cứ tiếp tục như vậy sau hữu
hạn bước ta xác đinh được đường đi ngắn nhất từ s tới f.
Áp dụng thuật toán Ford-Bellman
Bước 1: Khởi tao xuất phát từ đỉnh s. Gọi d[v] là khoảng cánh từ s tới v khởi
tạo d[s]=0; d[v]:=a[s,v].
Bước 2: Lặp

2.1 Tối ưu hóa dần d[v] như sau: Xét mọi cặp đỉnh (u,v) của đồ thị nếu
d[v]>d[u]+a[u,v] thì đặt d[v]=d[u]+a[u,v] và t[v]=u. (mảng t lưu vết đường đi)

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

17

2.2 Bước lặp kết thúc khi không thể tối ưu thêm bất kì một nhãn d[v] nào nữa,
dùng biến stop để kiểm soát quá trình này.
Procedure Ford_Bellman;
Begin
for
for (  v V) do begin d[v]:=a[s,v]; t[v]:=s; end;
d[s]:=0;
repeat
stop:=true;
for (  u V) do
for (  v V) and (u,v) E do
if d[v]>d[u]+ a[u,v] then
begin
d[v]>d[u]+ a[u,v]
stop:=false; t[v]:=u;
end;
until stop;
End;
Ví dụ: Cho đồ thi G=(V,E). Tìm đường đi ngắn nhất từ đỉnh A đến F
7

A

4

C

E

1

2
2

3
4

2
D

B

F

Ta kí hiệu t[v] là đỉnh trước của v trên đường đi từ A tới F. Minh họa kết quả
tính toán của thuật toán Ford-bellman qua bảng sau:
Bước
1
2
3
4

5

d[a],t[a]
0,a
0,a
0,a
0,a
0,a

d[b],t[b]
2,a
2,a
2,a
2,a
2,a

d[c],t[c]
7,a
6,a

d[d],t[d]
∞,a
∞,a

6,a
6,a
6,a

7,c
7,c

7,c

Số hóa bởi Trung tâm Học liệu - ĐHTN

d[e],t[e]

d[f],t[f]

∞,a
∞,a
10,c
9,d
9,d

∞,a
∞,a
∞,a
∞,a
12,e

/>

18

1.3.2 Tối ƣu hệ thống mạng truyền dẫn.
Bài toán tìm đường đi ngắn nhất là một bài toán khá quan trọng trong quá
trình thiết kế và phân tích mạng. Hầu hết các bài toán định tuyến có thể giải quyết
như giải quyết bài toán tìm đường đi ngắn nhất khi một “độ dài” thích hợp được gắn
vào mỗi cạnh (hoặc cung) trong mạng. Trong khi các thuật toán thiết kế thì cố gắng
tìm kiếm cách tạo ra các mạng thỏa mãn tiêu chẩn độ dài đường đi.

Ta xét các graph hữu hướng và giả sử rằng đã biết độ dài của một cung giữa
mỗi cặp nút i và j là lij. Các độ dài này không cần phải đối xứng. Khi một cung
không tồn tại thì độ dài lij được giả sử là rất lớn (chẳng hạn lớn gấp n lần độ dài
cung lớn nhất trong mạng). Chú ý rằng có thể áp dụng quá trình này cho các mạng
vô hướng bằng cách thay mỗi cạnh bằng hai cung có cùng độ dài. Ban đầu giả sử
rằng lij là dương hoàn toàn; sau đó giả thiết này có thể được thay đổi.
Phần lớn các mạng chuyển mạch gói sử dụng các thuật toán khác nhau của
phương pháp chọn tuyến đường ngắn nhất do lớp mạng thực hiện. Một số mạng
chọn tuyến theo cách thức tập trung, thiết lập đường dẫn giữa nút nguồn và nút đích
ở trung tâm điều hành mạng NMC (Network Management Center) hay trung tâm
điều khiển chọn tuyến RCC (Routing Control Center) rồi sau đó phân phối các
thông tin chọn tuyến đến tất cả các nút chuyển mạch trong mạng. Các nút mạng
khác sử dụng cách thức phi tập trung hay còn gọi là cách thức phân bố, từng nút
trao đổi thông tin chọn tuyến và giá thành với các nút khác trong mạng trên cơ sở
tương tác cho đến khi các bảng định tuyến đáp ứng được yêu cầu định tuyến ngắn
nhất.
Xét mạng như hình 1.11, trên mỗi đường ghép nố i có các tro ̣ng số tương ứng
với giá thành của từng đường , để đơn giản ta coi các trọng số này theo cả hai chiều
là như nhau , mă ̣c dù trên thực tế chúng có thể khác nhau về giá tri ̣ . Để cho ̣n đươ ̣c
đường dẫn ngắ n nhấ t t ừ một nguồn tới tất cả các nút trong mạng , đòi hỏi phải có
kiế n thức về cấ u hiǹ h tổ ng thể của ma ̣ng

(danh sách các nút và các ghép nố i giữa

chúng) cũng như giá thành của từng đường nối . Điề u đó dẫn tới viê ̣c tính t oán tập

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

19

trung dựa trên thông tin đầ y đủ lưu trong các cơ sở dữ liê ̣u trung tâm

(Central

Database).

Hình 1.11 Mô hình một mạng.
Thuâ ̣t toán đươ ̣c thực hiê ̣n theo từng bước , xây dựng mô hình cây đường ngắ n
nhấ t (Shortest Path Tree) có gố c ta ̣i nút nguồ n (nút 1). Các đường dẫn ngắn nhất tới
k nút khác đươ ̣c tính toán trong k bước, chúng được tập hợp lại trong tập N.
Coi D (v) là khoảng cách (tổ ng của các tro ̣ng số đường nố i do ̣c theo đường
dẫn) từ nút n guồ n 1 tới nút v . Coi l(i,j) là giá thành đã cho giữa 2 nút i và j . Thuâ ̣t
toán gồm 2 bước:
1.Bước khởi đầ u
Đặt N ={1} (tâ ̣p N ban đầ u chỉ gồ m duy nhấ t

1 nút), với mỗi nút v  N đă ̣t

D(v)=l(l,v), với các nút không nố i trực tiế p với nút l ta coi giá thành bằ ng  .
2.Bước lặp
Tìm nút w không thuộc N sao cho D (w) là tối thiểu và bổ sung w vào tập N .
Sau đó thay D(v) cho toàn bô ̣ các nút không thuô ̣c N còn la ̣i bằ ng cách tin
́ h:
D(v)min[D(v),D(w) + l(w,v)]
Bước này đươ ̣c lặp la ̣i cho đế n khi tấ t cả các nút đề u có trong N.
Sau khi thực hiê ̣n, ta lầ n lươ ̣t có đươ ̣c các bước mô tả bởi bảng thố ng kê sau:

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

20

Bước

Tâ ̣p N

D(2)

D(3)

D(4)

D(5)

D(6)

0

{1}

2







5

1

{1,2}

2

3





3

2

{1,2,3}

2

3

4

5

3

3

{1,2,3,6}

2

3

4

5

3

4

{1,2,3,6,4}

2

3

4

5

3

5

{1,2,3,6,4,5} 2

3

4

5

3

Mô hiǹ h cây đường đi ngắ n nhấ t nế u lấ y nút 1 làm nút nguồn có thể mô tả như
hình vẽ sau:

Hình 1.12.Mô hình đường dẫn ngắ n nhấ t .
Đić h

Nút tiế p theo

2

2

3

3

4

4

5

5

6

3

Hình 1.13. Bảng chọn tuyến cho nút 1.
Với thuâ ̣t toán này ta có thể tin
́ h đươ ̣c các tuyế n đường có đường dẫn ngắ n
nhấ t cho từng nút, cụ thể ta coi nút đó là nút nguồn rồi thực hiện các bước giải thuật
kể trên. Trong trường hơ ̣p cho ̣n tuyế n theo phương thức tâ ̣p trung, NMC sẽ gửi các
bảng chọn tuyến cho từng nút một sau khi đã thiết lập xong , còn nếu mạng sử dụng

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

21

phương thức phân bố thì từng nút phải tin
̣ tuyế n , cùng sử dụng các
́ h lấ y bảng đinh
thông tin tổ ng thể như trên (đươ ̣c cung cấ p bởi các nút lân câ ̣n hoă ̣c bởi NMC ) và
chọn ra cây đường dẫn cho riêng nó.

Chƣơng II: ĐƢỜNG ĐI NGẮN NHẤT TỪ MỘT ĐỈNH
Một người lái xe muốn tìm một đường đi ngắn nhất có thể từ Hà Nội đến Hải

Dương. Từ một bản đồ các tuyến đường của Việt Nam trên đó khoảng cách giữa các
ngã đường kề nhau cho trước, làm thế nào chúng ta có thể xác định được đường đi
ngắn nhất này.
Một cách có thể là liệt kê tất cả các tuyến đường từ Hà Nội đến Hải Dương,
tính độ dài đường đi trên mỗi tuyến đường, và chọn đường đi ngắn nhất. Dễ thấy
rằng, mặc dù chúng ta không kể đến những đường đi có chứa chu trình, vẫn có hàng
triệu khả năng có thể, hầu hết trong chúng là những đường đi không đáng để chúng
ta xem xét. Ví dụ, một đường đi từ Hà Nội qua Sài Gòn đến Hải Dương là một lựa
chọn tồi vì Sài Gòn ở cách xa đường đi ngắn nhất đến hàng nghìn dặm.
Trong chương này chúng ta sẽ chỉ ra làm thế nào để giải quyết những bài toán
như vậy một cách hiệu quả. Trong một bài toán tìm đường đi ngắn nhất, chúng ta
được cho trước một đồ thị định hướng có trọng số G = (V,E), với hàm trọng số w :
ER ánh xạ các cạnh của đồ thị vào tập các số thực. Trọng số của một đường đi
p = <v0, v1, ... , vk> là tổng của trọng số của các cạnh tạo thành đường đi đó.
k

w( p )   w(v i 1 , v i )
i 1

Chúng ta định nghĩa trọng số đường đi ngắn nhất từ một đỉnh u đến một đỉnh v như
sau:

Một đường đi ngắn nhất từ một đỉnh u đến một đỉnh v được định nghĩa là một
đường đi bất kì p mà có w(p) = (u,v).

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

22

Các biến thể
Trong chương này, chúng ta sẽ tập trung vào bài toán tìm đường đi ngắn nhất
từ một đỉnh: cho trước một đồ thị G = (V,E), chúng ta muốn tìm một đường đi ngắn
nhất từ một đỉnh nguồn cho trước s  V đến mỗi đỉnh v  V. Có rất nhiều bài toán
có thể giải được bằng thuật toán cho bài toán tìm đường đi ngắn nhất từ một đỉnh,
trong đó có các biến thể sau đây:
-

Tìm đường đi ngắn nhất đến một đỉnh

-

Tìm đường đi ngắn nhất giữa một cặp

-

Tìm đường đi ngắn nhất giữa tất cả các cặp

Bổ đề (Đoạn con của đƣờng đi ngắn nhất là một đƣờng đi ngắn nhất)
Cho một đồ thị có trọng số G = (V,E) với hàm trọng số w : E  R, p =... , vk> là một đường đi ngắn nhất giữa các đỉnh v1 và vk. Khi đó với mọi i, j thoả
mãn 1 i  j  k, ta có pij = <vi, vi+1, ... , vj> là một đường đi ngắn nhất từ vi đến vj.
Chứng minh
p
 vi  v j  vk , khi đó ta có
Nếu chúng ta tách đường đi p thành v1 
pij

1i

p jk

w(p) = w(p1i) + w(pij) + w(pjk). Giả sử có một đường đi ngắn nhất p’ij từ vi đến vj
p
 vi  v j  vk là một đường đi
với trọng số w(p’ij) 1i

p 'ij

p jk

từ v1 đến vk mà có trọng số là w(p1i) + w(p’ij) + w(pjk) nhỏ hơn w(p), mâu thuẫn
với giả thiết p là một đường đi ngắn nhất từ v1 đến vk.
Cạnh với trọng số âm
Trong một số trường hợp cụ thể của bài toán tìm đường đi ngắn nhất từ một
đỉnh, có thể có các cạnh của đồ thị mà trọng số của nó là một số âm. Nếu đồ thị G=
(V,E) không chứa các chu trình trọng số âm có thể đi đến được từ một đỉnh s, khi đó
với mọi đỉnh vV, trọng số đường đi ngắn nhất (s,v) hoàn toàn xác định, ngay cả
khi nó có giá trị âm. Nếu có một chu trình trọng số âm có thể đi đến được từ đỉnh s,
trọng số đường đi ngắn nhất không được xác định. Không có một đường đi nào từ s
đến một đỉnh trên chu trình đó là đường đi ngắn nhất - một đường đi với trọng số

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>