SONG SONG HÓA THU T TOÁN DIJKSTRA TÌM Đ

NG ĐI NG N NH T Ắ

Ấ

Ấ

Ả

Ế

Ỉ

Ậ Ừ Ộ

ƯỜ Ỉ

T M T Đ NH Đ N T T C CÁC Đ NH PARALLELIZING ALGORITHM DIJKSTRA’S FINDING THE SHORTEST PATHS FROM A VERTEX TO ALL VERTICES

ạ ọ

ễ

PGS.TS Lê M nh Th nh – Đ i h c Hu ạ ế ạ Nguy n Đình L u - NCS Đ i h c Đà N ng ẵ ạ ọ ầ t - NCS Đ i h c Đà N ng Tr n Ng c Vi ẵ ạ ọ ệ

ầ

ọ

TÓM T TẮ

ủ

ng đi ng n nh t t ắ

ự

ng c a thu t toán là s d ng m b

ả ế ấ ả

ườ ậ

ưở

ủ

ậ t c các đ nh d a trên thu t toán tu n t ườ

ỉ ng đi ng n nh t t ắ

ậ Dijkstra. Ý t ỉ ữ ệ

ử ụ ộ ử ọ

ệ

ả

ậ

m t ấ ừ ộ K t qu chính c a bài báo là t p trung xây d ng thu t toán song song tìm đ ế ộ đ nh đ n t ự ậ ỉ t c các đ nh trên trên đ th . Trong m b x lý ch n x lý tìm đ ọ ấ ừ ộ ỉ ồ ị ử ố ủ m t b x lý đóng vai trò trung tâm th c hi n vi c qu n lý d li u, chia n đ nh và ma tr n tr ng s c a ỉ ự ộ ộ ử đ th cho m b x lý đ tìm đ ồ ị

ầ ự m t đ nh đ n t ế ấ ả ệ ng đi ng n nh t. ấ ắ

ộ ử

ườ

ể

ABSTRACT

The main result of this article is building parallel algorithm finding the shortest paths for a vertices to all vertices based on Dijkstra algorithm. The idea of this algorithm is using m processors to find the shortest paths for a vertice to all vertices in a graph. Among k processors, we choose one central processor playing a role in managing data, dividing n vertices and weight matrix into m processors to find the shortest paths.

1. Đ t v n đ ặ ấ ề

ọ ạ ớ t c các đ nh là m t trong s nh ng bài toán t i u trên đ th tìm đ ỉ ọ ộ ồ ị ố ư ượ cũng nh nh ng ng d ng thú v trong toán h c r i r c. Bài toán đ ị ố ữ ụ i Hà Lan ư ữ ứ ườ ế ở ả ọ ọ ậ ề ế ắ ấ ng trình, t c đ x lý, kh năng l u tr ắ ng đi ng n ườ c nh ng ng ữ ứ c đ xu t ấ ượ ề c g i là thu t toán Dijkstra . i quy t nh ng v n đ b t c mà mô ữ ữ ộ ử ọ ờ ạ Edsger Dijkstra và đ ượ ế ố ử ầ ự ặ ẽ ả ươ ạ ệ ể ự ư ả ả Cho đ th liên thông G(V,E,w) có tr ng s w(i,j) >0 v i m i c nh (i,j). Bài toán tìm đ ố ồ ị m t đ nh đ n t nh t t ế ấ ả ấ ừ ộ ỉ d ng r ng rãi trong th c t ộ ự ế ụ và gi i quy t b i nhà khoa h c máy tính ng Hi n nay, mô hình x lý song song đã và đang phát tri n m nh m gi ệ g p ph i nh v n đ th i gian th c hi n ch hình x lý tu n t ề ờ ư ấ ử c a b nh , x lý d li u v i quy mô l n. ớ ữ ệ ủ ộ ớ ử ớ

ố ả ự ậ ậ trên đ th v i m b x lý nh m kh c ph c đ c các v n đ t n t ế ấ ả ồ ị ớ ỉ “song song thu t toán Dijkstra tìm đ ắ ộ ử ụ ượ ằ ườ ấ ắ ng đi ng n ề ồ ạ i nh t t đã nêu Trong b i c nh đó chúng tôi xây d ng thu t toán m t đ nh đ n t t c các đ nh” ấ ừ ộ ỉ trên. ở

2. Thu t toán tu n t Dijkstra tìm đ m t đ nh đ n t t c các đ nh ầ ự ậ ườ ng đi ng n nh t t ắ ấ ừ ộ ỉ ế ấ ả ỉ

˛),( j i E

Đ u vào: Đ th liên thông G(V,E,w), w(i,j) ≥ 0 Đ u ra: Chi u dài đ ng đi ng n nh t và đ , đ nh ngu n a. ồ a đ n t ồ ị ề ng đi ng n nh t t ắ ỉ ấ ừ ườ ườ ấ ắ ế ấ ả t c các đ nh trên đ th . ồ ị ỉ +Ph ớ ọ ỉ ˛ ươ B B ầ ầ ng pháp: c 1ướ : Gán L(a):=0. V i m i đ nh x ≠ a gán L(x)= ∞. Đ t T:=V. c 2ướ : Ch n v ư ấ ọ ặ T, v ch a xét sao cho L(v) có giá tr nh nh t, Đ t T:=T\{v}, đánh d u đ nh v ỏ ặ ấ ị ỉ đã xét.

f , K t thúc, L(z), c ghi nh ta có đ ườ ớ

" ế ấ ừ ườ ề ế ế

c ghi nh lên các nhãn

z˛ V, z≠a là chi u dài đ ấ ừ a đ n z. T z ồ ng đi ng n nh t. (L(z) không thay đ i (L(z)= ∞ thì không t n ng đi ng n nh t t ắ ổ ắ B ượ l n ng ầ i đ t ạ ườ c 4. ˛ ớ ề ế ướ ớ đ nh v c nh đ nh x b ng m ng truoc[] (v i truoc[] c a đ nh 1=0) đ sau này xây d ng đ ỉ T k v gán L(x):=min{L(x), L(v)+w(v,x)}. N u L(x) thay đ i thì ghi nh ể ổ ng đi ng n nh t. ấ ắ ườ ự ủ ỉ ớ

ự

ễ

ệ

ế

ậ

ả ượ

ớ

ng ng.

ằ c 2.[3] c bi u di n sau đây, sau khi thu t toán th c hi n xong thì k t qu đ ể c 3ướ : N u T= c theo đ nh đ ượ ỉ ng đi_Not Path)). c l i sang b Ng ướ ượ ạ V i m i x c 4: B ỗ ỉ ả ạ ề ướ ồ ị ượ

Quay v b Ví d :ụ Cho đ th đ đ nh t ươ ứ ỉ

(7)1 (0) 7 (38)8 9 1 2

4 5 6 1 7

20 (13)2 18 11 (5)1 4 3 (18)4 5 8 4 10 6 6 10 10 15

(15)3 5 6 (15)3 10

2 11 1 0 (39)11 0 15 20 (24)7 5 7 (29) 11 7

(17)6 Hình 1. Ghi nh k t qu tính đ ớ ế ả ượ

1 c trên đ th ồ ị 2 2

ng đi, v i truoc[1]=0) ể ả ớ ườ ớ ộ t c các đ nh là: M ng truoc[]=0 1 1 2 3 3 6 4 8 11 7 11 (M ng ghi nh truoc [] dùng đ tìm đ M ng đ dài L = 0 7 5 13 15 15 17 18 38 39 24 29 V y k t qu t ế ả ả ậ ỉ ế ấ ả

đ nh 1 đ n t 2) 3) 24) 35) 36) 367) 248) 248) 3671110) 36711) 3671112) ả ừ ỉ đ n 2=7 (1 ế đ n 3=5 (1 ế đ n 4=13 (1 ế đ n 5=15 (1 ế đ n 6=15 (1 ế đ n 7=17 (1 ế đ n 8=18 (1 ế đ n 9=38 (1 ế đ n 10=39 (1 ế đ n 11= 24 (1 ế đ n 12=29 (1 ế

3. Thu t toán song song Dijkstra ậ

" Đ u vào: Đ th liên thông G(V,E,w), w(i,j) ≥ 0 (i,j)˛ E, đ nh ngu n a, 1 b x lý chính và m b ồ ị ầ ộ ử ồ ỉ ộ

x lý ph . ụ ử

Đ u ra: Chi u dài đ ng đi ng n nh t và đ a đ n t ề ầ ườ ấ ắ ườ ng đi ng n nh t t ắ ấ ừ ế ấ ả t c các đ nh trên đ th . ồ ị ỉ

0, P1,…,Pm-1), trong cùng tính toán đ ng th i, m i b BXL

+Ý t ng: ưở Chia đ th ban đ u cho m b x lý(P ầ ộ ử ồ ị ỗ ộ ồ ờ

đ m nh n n/m đ nh c a đ th (n là s đ nh c a đ th , m là s BXL ph ) và ma tr n tr ng s n/m c t và n ả ủ ồ ị ủ ồ ị ố ỉ ụ ậ ậ ố ọ ố ộ ỉ

dòng (n u n chia h t cho m). ế ế

+Ph ng pháp: ươ

B c 1ướ : B x lý chính th c hi n ộ ử ự ệ

- Gán L(a):=0. V i m i đ nh x ≠ a, x thu c b x lý chính gán L(x)= ∞. ộ ộ ử ọ ỉ ớ

- Chia đ u s đ nh và ma tr n tr ng s đ g i cho m BXL. ề ố ỉ ố ể ử ậ ọ

0,P2,…,Pm-1.

i (i=0,…,m-1).

s ta có n đ nh và m b x lý P Cách chia đ u nh sau: gi ề ư ả ử ộ ử ỉ

G i nọ i là s đ nh c a b x lý P ủ ộ ử ố ỉ

- N u n chia h t cho m thì ế ế

ni - N u n không chia h t cho m thì

/= mn ế

For i=0 to m-1 do

ế

=

ni

( mn

).1

n m -=-

nm

1

n m

i (i=0,…,m-1) là t p đ nh mà b x lý P

i s nh n nh sau:

For i=0 to m-2 do ø Ø œ Œ ß º ø Ø - œ Œ ß º

- Ta xây d ng Tự ộ ử ậ ỉ ư ẽ ậ

BN=0; kt là s ph n t ầ ử ố mà các b x lý nh n ậ ộ ử

for (k=0; k

n Tk=f ; BN=k* m

{ ø Ø œ Œ ß º for (j=0; j

Tk=Tk+{j+ BN+1}

i (i=0,…,m-1) là ma tr n tr ng s mà b x lý P

i s nh n nh sau:

}

- Ta xây d ng Aự ộ ử ậ ọ ố ư ẽ ậ

ij)nxn.

G i A là ma tr n tr ng s c a đ th đ u vào thì A=(w ố ủ ồ ị ầ ậ ọ ọ

w

w

w...

11

12

1n

w

w

w...

=

A

2n ..

22 .......... w...

21 .......... ww n 1

n2

nn

ø Ø œ Œ œ Œ œ Œ œ Œ ß º

Hình 2. Ma tr n tr ng s c a đ th ố ủ ồ ị ọ ậ

(

)

=

i (i=0,…,m-1) nh nậ

ẽ ượ ộ ử

A i

= ,1

k

; iTjn

˛

w Suy ra S đ c b x lý P kj - G i Tử i (i=1,..,m-1), Ai (i=1,…,m-1), L(x), x˛ Ti (i=1,…,m-1), cho m-1 BXL ph Pụ 1,P2,…,Pm-1.

B c 2: m b x lý ướ ộ ử th c hi n ự ệ

i (i=1,…,m-1)

- Trong m b x lý(tr b x lý chính), gán L(x ừ ộ ử ộ ử

i)= ∞, sao cho xi thu c Tộ ˛ Ti (i=0,…,m-1), xi ch a xét}

i(xi)=min{L(xi), xi

- Trên m b x lý tìm L ư ộ ử

- Các b x lý ph g i L ụ ử i(xi) v b x lý chính ề ộ ử ộ ử

B c 3: B x lý chính th c hi n ướ ộ ử ự ệ

= m ,0

i

1

i(xi),

- - B x lý chính tìm l(v)=min {L }trên m b x lý. ộ ử ộ ử

c ti p theo - Chuy n đ nh v lên m b x lý đ th c hi n các b ộ ử ể ự ể ệ ỉ ướ ế

B ướ ộ ử ự

c 4: m b x lý th c hi n ệ iT˛ - Trên m BXL ki m tra n u v , Ti=Ti\{v} (i=0,…,m-1), đánh đ u đ nh v đã xét. ế ỉ

c 6 - Ki m tra n u T ể ấ i (i=0,..,m-1)= f , thì b x lý th i k t thúc sang b ộ ử ướ ứ ế ể ế

- Ng i sang b c 5. c l ượ ạ ướ

B c 5: m b x lý th c hi n ướ ộ ử ự ệ for x ˛ Ti (i=0,…,m-1) k v i ề ớ v if L(x)>L(v)+w(v,x) { L(x) := L[v] + w(v,x) ớ ỉ Truoc[x]=v // ghi nh đ nh v vào x }

quay l i b ạ ướ . c 2

B c 6ướ : B x lý chính th c hi n ộ ử ự ệ

N u t ế ấ ả t c m-1 b x lý ph k t thúc thì b x lý chính th c hi n: nh n k t qu t ộ ử ụ ế ộ ử ả ừ ự ệ ế ậ ộ ử các b x lý

a đ n t t c các đ nh và đ ph và k t lu n chi u dài đ ậ ụ ế ề ườ ng đi ng n nh t t ắ ấ ừ ế ấ ả ỉ ườ ng đi ng n nh t qua các đ nh ấ ắ ỉ

đã ghi nh . Đ nh nào có nhãn không thay đ i (b ng ∞) thì không t n t ớ ỉ i đ ồ ạ ườ ằ ổ ệ ố ng đi_Not Path)). H th ng

k t thúc. ế

t c các đ nh theo thu t toán song song c a đ th Ví dụ: Tìm đ ườ ng đi ng n nh t t ắ ấ ừ ỉ đ nh ngu n a=1 đ n t ồ ế ấ ả ủ ồ ị ậ ỉ

1 là b x lý ph . ụ

(n=12 đ nh) d i đây (trên m=2 b x lý ph (P ỉ ướ ộ ử ụ 0, P1) trong đó P0 là b x lý chính, P ộ ử ộ ử

B

c 1ướ : B x lý chính P ộ ử

0 th c hi n ệ

ự

Phân T0={1,2,3,4,5,6} A0 cho chính P0, phân T1={7,8,9,10,11,12}, A1 cho P1

gán L(1)=0; L(2)=L(3)=L(4)=L(5)=L(6)

10

5 7 4

6 7 1 6

10 11

20 2

5

15

10

=

A

10

20

4 18

7 15 5

6

¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ø Ø œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ß º

Hình 3. Ví d v ma tr n tr ng s c a đ th ố ủ ồ ị ậ

ụ ề

ọ

5 7

6 7

4

1

10 11

10

5

20

=

=

6

2

15

10

0A

1A

7

10

20

4 18

15

6

5

¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ø Ø ø Ø œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ œ Œ œ Œ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ß º ß º

0 và A1 mà 2 b x lý nh n

Hình 4. Ma tr n Aậ

ộ ử

ậ

0 nh n đ nh a=1, L(1)=0, L(2)=L(3)=L(4)=L(5)=L(6)=∞,

ậ

ỉ

0 th c hi n g i L(7)=L(8)=L(9)=L(10)=L(11)=∞,

B x lý chính P ộ ử T0={1,2,3,4,5,6} và A0 . B x lý chính p ộ ử

1.

ự ệ ử ế ộ ử

0 th c hi n

ự

c 2:

ộ ử ướ

T1={7,8,9,10,11,12} và A1 đ n b x lý P B x lý P ệ B Tìm minl=min{L(x), x ˛ T0}  minl=0, iminl=0

1 th c hi n

ự

ệ

ộ ử ướ

B x lý P B c 2: Gán L(7)=L(8)=L(9)=L(10)=L(11)=L(12)= ∞

Tìm minl=min{L(x), x ˛ T1}= ∞

ử

0 th c hi n

ự

c 3:

Tìm min c a minl đã chuy n đ n

c 2 v i minl mà P

G i minl v P ề 0 B x lý P ệ B ủ

ộ ử ướ

b ế ở ướ

ể

ớ

0 giữ

ỉ

 Min=Lv=L(1)=0, gán đ nh v=1 Chuy nể v=1 lên P0 và P1 ,

0 th c hi n

ệ

ự

ộ ử ướ

ấ

ỉ

c 5.

f

ướ

„

B x lý P c 4: B T0=T0\{v}={1,2,3,4,5,6}\{1}={2,3,4,5,6}, đánh d u đ nh 1 đã xét. sang b 0T

0 th c hi n

ự

ệ

ộ ử ướ

Đ nh 2,3 k v i đ nh 1.

B X lý P c 5: B ỉ

ề ớ ỉ

L(2)=min{L(2), w(1,2)+L(1)}=7 thay đ i.ổ L(3)=min{L(3), w(1,3)+L(1)}= 5 thay đ i.ổ Ghi nh đ nh 1 vào đ nh 2,3 đ th có các nhãn nh sau: ỉ

ồ ị

ớ ỉ

ư

(0) (7)1 7 1 2

4 5 6 1 7

(∞) 18 (∞) 11 4 3 (5)1 8 4 10 6 10 10

(∞) (∞) 5 6

0)

ồ ị

ộ ử

1 th c hi n

ự

Hình 5. Đ th ghi nh trên b x lý chính (P ớ ệ

B x lý P B

c 4:

ộ ử ướ

, suy ra T1={7,8,9,10,11,12}.

1Tˇ

c 5.

„

v=1, đ nh 1 ỉ , sang b ướ 1T B c 5:

f ướ

không có đ nh nào k v i đ nh 1.

ề ớ ỉ

ỉ

Đ th có nhãn không thay đ i ổ

ồ ị

(∞)

9

20 (∞)

(∞) 4 5 8

6 (∞) (∞) 15 (∞) 6 5 10 (∞) 15 2 11 1 0 0 20 5 (∞) 7 7 (∞)

Hình 6. Đ th ghi nh trên b x lý ph (P ớ

ồ ị

ộ ử

ụ 1)

1 2 0

0 th c hiên

ự

ử ề ộ ử

0 tìm minl=min{L(2), L(3), L(4),L(5),L(6)}= L(3)=5, g i v b x lý chính. 1 th c hiên

ự

ử ề ộ ử

1 tìm minl=min{L(7), L(8), L(9),L(10),L(11),L(12)}= ∞, g i v b x lý chính. 0 th c hi n

ự

ệ

ộ ử ướ ộ ử ộ ử ướ ộ ử ộ ử ướ

c 2 v i minl mà P

ủ

ể

ớ

0 giữ

B x lý P B c 2: B x lý P B x lý P B c 2: B x lý P B x lý P b c 3: Tìm min c a minl đã chuy n đ n ỉ

b ế ở ướ  Min=Lv=L(3)=5, gán đ nh v=3 Chuy nể v=3 lên P0 và P1 ,

0 th c hi n

ự

ệ

B x lý P c 4: B

ộ ử ướ

T0=T0\{v}={1,2,3,4,5,6}\{3}={2,4,5,6}, đánh d u đ nh 1 đã xét.

ấ

ỉ

c 5.

f

ướ

„

sang b 0T

b x lý chính P

i đây

ẽ ậ ế

ả ượ

c bi u di n nh trong đ th d ư

ồ ị ướ

ể

ễ

0 th c hi n

ự

c 5:

0 s nh n k t qu đ ệ ề ỉ

- Ở ộ ử B x lý P ộ ử B đ nh 4,5,6 k đ nh 3 ỉ ướ L(4)=min{L(4),w(3,4)+L(3)}=16 thay đ iổ L(5)=min{L(5),w(3,5)+L(3)}=15 thay đ iổ L(6)=min{L(6),w(3,6)+L(3)}=15 thay đ iổ

c 2

i b ạ ướ

1 th c hi n

ỉ ệ

ự

Ghi nh đ nh 3 vào đ nh 4,5,6 . Quay l ớ ỉ B x lý P B

c 4:

ộ ử ướ

, suy ra T1={7,8,9,10,11,12}.

1Tˇ

„

c 5. 1 th c hi n

ệ

v=3, đ nh 3 ỉ , sang b ướ f 1T B x lý P ộ ử ự c 5: B ướ

ỉ

ề ớ ỉ

ổ

c k t qu

ướ

ả ở

ư

không có đ nh nào k v i đ nh 3. Đ th có nhãn không thay đ i. ồ ị Quay l c 2. i b ạ ướ C ti p t c các b ứ ế ụ b x lý ph P Ở ộ ử

c trên cho hai b x lý ta thu đ ượ ế c bi u di n nh trong đ th d ụ 0 s nh n k t qu đ ư ễ ẽ ậ ế

hai b x lý nh sau ộ ử i đây ồ ị ướ

ộ ử ả ượ

ể

(0) (7)1 7 1 2

4 5 6 1 7

(∞)

18 11 4 3 (5)1 (13)2 8 4 10 6 10 10

6 5 (15)3

ồ ị

-

b x lý ph P

i đây

Ở ộ ử

(15)3 Hình 7. Đ th ghi nh trên b x lý chính (P ớ ụ 1 s nh n k t qu đ ẽ ậ ế

0) ồ ị ướ

ả ượ

ể

ộ ử c bi u di n nh trong đ th d ư ễ (38)8

9

20 (∞)

(18)4 4 5 8

6 (39)11 (∞) (∞) 15

6 5 10 (24)7

2 15 11 20 5 1 0 0 (29) 11 7 7 (17)6 1 2

1)

Hình 8. Đ th ghi nh trên b x lý chính (P ớ

ồ ị

ộ ử

B

c 6:

ướ

B x lý chính ki m tra b x lý ph k t thúc thì b x lý chính s nh n đ ụ ế

ẽ ậ ượ c

ộ ử

ộ ử

ộ ử

ể

k t qu mà b x lý ph g i đ n và hi n th k t qu theo yêu c u. K t thúc h th ng. ế

ụ ử ế

ệ ố

ộ ử

ị ế

ể

ế

ả

ầ

ả

(7)1 (0) 7 (38)8 9 1 2

4 5 6 1 7

20 (13)2 18 11 (5)1 4 3 (18)4 5 8 4 10 6 6 10 10 15

(15)3 5 6 (15)3 10

2 11 1 0 (39)11 0 15 20 (24)7 5 7 (29) 11 7

(17)6 1 2 Hình 9. Đ th hi n th k t qu cu i cùng

ồ ị ể

ả ố

ị ế

4. K t qu Demo ế ả

B x lý chính (P ộ ử

ng đi ) ghi nh các ớ 0 đ nh đ tìm đ ườ ể ỉ

B x lý ph (P ộ ử ụ

ng đi ) 1 đ nh đ tìm đ ể ỉ ghi nh các ớ ườ

B x lý chính (P ộ ử ừ

tìm chi u dài t ) ề 0 đ nh 1 đ n các đ nh 1, 2, 3, 4, 5, 6 ỉ ỉ ế

B x lý ph (P đ nh ộ ử ụ ừ ỉ ) 1 tìm chi u dài t ề 1 đ n các đ nh 7, 8, 9, 10, 11, 12 ế ỉ

Hình 10. K t qu Demo ế ả

Chúng tôi ch y th nghi m v i đ th 200 đ nh trên 1,2,4,6,8 b x lý thì k t qu đ c cho nh hình ớ ồ ị ộ ử ả ượ ử ế ệ ạ ỉ ư

10.

5. K t lu n ế ậ

V i vi c song song hóa thu t toán tu n t Dijstra tìm đ m t đ nh đ n t t c ầ ự ệ ậ ớ ườ ng đi ng n nh t ắ ấ t ừ ộ ỉ ế ấ ả

i quy t đ c các v n đ b t t mà thu t toán tu n t g p ph i nh th i gian, d các đ nh s giúp ta gi ẽ ỉ ả ế ượ ề ế ắ ấ ầ ự ặ ư ờ ả ậ ữ

li u đ u vào, tuy nhiên đ cài đ t thu t toán này đòi h i ph i có c m máy tính song song, c th trong bài ụ ể ụ ệ ể ả ặ ầ ậ ỏ

báo này tôi dùng cum máy tính song song c a Tr ủ ườ ậ ng Đ i H c S Ph m Hà N i đ ch y Demo. Thu t ộ ể ư ạ ạ ạ ọ

toán cho k t qu v i th i gian x lý nhanh h n thu t toán tu n t ử ả ớ ầ ự ế ậ ơ ờ khi d li u đ u vào là l n . ầ ữ ệ ớ

[2]

[3]

[4]

[5]

ệ 6. Tài li u tham kh o ả [1] X lýử ễ ậ song song & phân tán, Vi n Công ngh Thông tin ệ ệ ế thu tậ ầ ự ạ , T p chí Khoa h c & Công ngh , Đ i h c Đà N ng, 5(22)/2007, 37- PGS.TS Đoàn Văn Ban, TS. Nguy n M u Hân, , 2006. PGS.TSKH Tr n Qu c ọ ố Chi n, H Xuân Bình, ồ ẵ ạ ọ ệ ạ ồ toán song song tìm lu ng c c đ i 42 PGS.TSKH Tr n Qu c Chi n, ầ ế Giáo trình Lý thuy tế ố đ thồ ị, Đ i h c Đà N ng 2007. ạ ọ ẵ ầ ầ ỹ ị PGS.TSKH Tr n Qu c Chi n, Tr n Th M Dung, ồ ng đi ng n nh t Đa ngu n đích tìm lu ng c c đ i đa hàng hóa đ ng ế ự Ứ ắ ạ “ ng d ng thu t toán tìm đ ấ th i”,ờ k y u h i th o khoa h c Công ngh Thông tin, Đ i h c S Ph m Đà N ng, 11-2011 ồ ạ ọ ư ụ ỷ ế ố ồ ạ ườ ọ ậ ộ ệ ẳ ả Tom Wilson, Nicholas Hofbauer, Dijkstra’s Algorithm in Parallel, team report 2008