Báo cáo thuật toán DIJKSTRA và xây dựng ứng dụng mô phỏng tìm đường đi ngắn nhất
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 (454.64 KB, 13 trang )
MỤC LỤC
MỤC LỤC........................................................................................................................................................1
LỜI NÓI ĐẦU..................................................................................................................................................3
CHƯƠNG I: THIẾT KẾ GIAO DIỆN............................................................................................................4
1 . Màn hình :..........................................................................................................................................4
CHƯƠNG 2.THUẬT TOÁN GIẢI QUYẾT BÀI TOÁN - THUẬT TOÁN DIJKSTRA.............................6
Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra, là một thuật
toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh
mang trọng số âm....................................................................................................................................6
Ta có thể giải bài toán bằng cách xác định một tập hợp S chứa các đỉnh mà khoảng cách ngắn nhất từ
nó đến đỉnh nguồn v đã biết. Khởi đầu S = { V }. Sau đó tại mỗi bước ta sẽ thêm vào S các đỉnh mà
khoảng cách từ nó đến v là ngắn nhất. Với giả thiết rằng mỗi cung có một giá trị không âm thì ta luôn
luôn tìm được một đường đi ngắn nhất như vậy mà chỉ đi qua các đỉnh đã tồn tại trong S. Ðể dễ dàng
chi tiết hóa giải thuật, giả sử G có n đỉnh và nhãn trên mỗi cung được lưu trong mảng C, tức là C[i, j]
bằng giá trị(có thể xem là độ dài) của cung (i, j). Nếu i và j không có cung nối thì ta cho C[i, j] =Ġ. Ta
sẽ dùng một mảng D có n phần tử để lưu độ dài của đường đi ngắn nhất từ v đến mỗi đỉnh của đồ thị.
Khởi đầu thì giá trị này chính là độ dài cạnh (v, i), tức D[i] = C[v, i]. Tại mỗi bước của giải thuật thì
D[i] sẽ lưu độ dài đường đi ngắn nhất từ đỉnh v đến đỉnh i, đường đi này chỉ đi qua các đỉnh đã có
trong S. 2/Cài đặt:...................................................................................................................................6
Ðể cài đặt giải thuật dễ dàng, ta giả sử các đỉnh của đồ thị được đánh số từ 1 đến n và đỉnh nguồn là
đỉnh.........................................................................................................................................................6
procedure Dijkstra; begin S := [1] ; { S chỉ chứa đỉnh nguồn } for i:=2 to n do D[i] := C[1, i] ; { Khởi
đầu các giá trị cho D } for i:=1 to n - 1 do begin Lấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ;
Thêm w vào S ; for mỗi đỉnh u thuộc V - S do D[u] := Min (D[u], D[w] + C[w, u]) ; end; end; <!--[endif]-->.......................................................................................7
Nếu muốn lưu trữ lại các đỉnh trên đường đi ngắn nhất để có thể xây dựng lại đường đi này từ đỉnh
nguồn đến các đỉnh khác, ta dùng một mảng P. Mảng này sẽ lưu P[u] = w với đỉnh u là đỉnh trước của
đỉnh w trên đường đi ngắn nhất. Lúc khởi đầu ta cho P[u] = 1, với mọi u khác 1. Giải thuật Dijkstra ở
trên sẽ được viết lại như sau : <!--[if !supportLineBreakNewLine]--> <!--[endif]-->...........................7
procedure Dijkstra ; begin S := [1] ; { S chỉ chứa đỉnh nguồn } for i:=2 to n do begin D[i] := C[1, i] ;
{ Khởi đầu các giá trị cho D } P[i] := 1 ; { Khởi đầu các giá trị cho P } end ; for i:=1 to n - 1 do begin
Lấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ; Thêm w vào S ; for mỗi đỉnh u thuộc V - S do if
(D[w] + C[w, u] < D [u]) then begin D[u] := D[w] + C[w, u] ; P[u] := w ; end ; end; end; 3/Ví dụ :.8
Áp dụng giải thuật Dijkstra cho đồ thị hình sau: <!--[if !supportLineBreakNewLine]-->......................9
procedure DijksTra;..............................................................................................................................10
begin.....................................................................................................................................................10
t:=false;................................................................................................................................................10
Tìm đường đi ngắn nhất
t[u0]:=true;...........................................................................................................................................10
d[i]:=c[u0,i];{Neu khong co duong di thi d[i]=i’}...............................................................................10
k:=1;{Da ket nap duoc 1 dinh}.............................................................................................................10
while kdo...............................................................................................................................................10
begin......................................................................................................................................................10
{Tim min}..............................................................................................................................................10
min:=i’;.................................................................................................................................................10
for i:=1 to n do......................................................................................................................................10
if (d[i]
u:=i;......................................................................................................................................................10
min:=d[u].............................................................................................................................................10
end;.......................................................................................................................................................10
t[u]:=true;{thêm u vao tập đỉnh}..........................................................................................................10
inc(k);....................................................................................................................................................10
{Tính lại đường đi}...............................................................................................................................10
for i:=1 to n do......................................................................................................................................10
if d[i]>d[u]+c[u,i] then........................................................................................................................10
if not((d[i]=i’)and(d[u]=i’)and(c[u,i]=i’)) then...................................................................................10
begin......................................................................................................................................................10
d[i]:=d[u]+c[u,i];................................................................................................................................10
truoc[i]:=u............................................................................................................................................10
end.........................................................................................................................................................11
end;........................................................................................................................................................11
if d[v0]=i’ then......................................................................................................................................11
KhongCoDuongDi.................................................................................................................................11
else........................................................................................................................................................11
QuayLaiMangTruocDeTimDuong.........................................................................................................11
end;........................................................................................................................................................11
Chương 3: Mô tả chung và code:.........................................................................................................11
KẾT LUẬN............................................................................................................................................13
2
Tìm đường đi ngắn nhất
LỜI NÓI ĐẦU
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 , 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...
3
Tìm đường đi ngắn nhất
CHƯƠNG I: THIẾT KẾ GIAO DIỆN
1 . Màn hình :
Màn hình này dùng để nhập vào các thông tin cơ bản là :
- Load Map
- Open
-Start
-Reset
-About, Exit
4
Tìm đường đi ngắn nhất
1.2 Màn hình chính
Gồm phần hiển thị thành phố,Thông tin,Kết quả,các chức năng
5
Tìm đường đi ngắn nhất
CHƯƠNG 2.THUẬT TOÁN GIẢI QUYẾT BÀI TOÁN - THUẬT TOÁN
DIJKSTRA
Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger
Dijkstra, là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn
trong một đồ thị có hướng không có cạnh mang trọng số âm.
1/Bài toán:
Ta có thể giải bài toán bằng cách xác định một tập hợp S chứa các đỉnh mà
khoảng cách ngắn nhất từ nó đến đỉnh nguồn v đã biết. Khởi đầu S = { V }.
Sau đó tại mỗi bước ta sẽ thêm vào S các đỉnh mà khoảng cách từ nó đến v là
ngắn nhất. Với giả thiết rằng mỗi cung có một giá trị không âm thì ta luôn
luôn tìm được một đường đi ngắn nhất như vậy mà chỉ đi qua các đỉnh đã tồn
tại trong S. Ðể dễ dàng chi tiết hóa giải thuật, giả sử G có n đỉnh và nhãn trên
mỗi cung được lưu trong mảng C, tức là C[i, j] bằng giá trị(có thể xem là độ
dài) của cung (i, j). Nếu i và j không có cung nối thì ta cho C[i, j] =Ġ. Ta sẽ
dùng một mảng D có n phần tử để lưu độ dài của đường đi ngắn nhất từ v đến
mỗi đỉnh của đồ thị. Khởi đầu thì giá trị này chính là độ dài cạnh (v, i), tức
D[i] = C[v, i]. Tại mỗi bước của giải thuật thì D[i] sẽ lưu độ dài đường đi
ngắn nhất từ đỉnh v đến đỉnh i, đường đi này chỉ đi qua các đỉnh đã có trong
S.
2/Cài đặt:
Ðể cài đặt giải thuật dễ dàng, ta giả sử các đỉnh của đồ thị được đánh số từ 1 đến n
và đỉnh nguồn là đỉnh
6
Tìm đường đi ngắn nhất
procedure Dijkstra;
begin
S := [1] ; { S chỉ chứa đỉnh nguồn }
for i:=2 to n do
D[i] := C[1, i] ; { Khởi đầu các giá trị cho D }
for i:=1 to n - 1 do
begin
Lấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ;
Thêm w vào S ;
for mỗi đỉnh u thuộc V - S do
D[u] := Min (D[u], D[w] + C[w, u]) ;
end;
end;
<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->
Nếu muốn lưu trữ lại các đỉnh trên đường đi ngắn nhất để có thể xây dựng lại
đường đi này từ đỉnh nguồn đến các đỉnh khác, ta dùng một mảng P. Mảng
này sẽ lưu P[u] = w với đỉnh u là đỉnh trước của đỉnh w trên đường đi ngắn
nhất. Lúc khởi đầu ta cho P[u] = 1, với mọi u khác 1.
Giải thuật Dijkstra ở trên sẽ được viết lại như sau :
<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->
7
Tìm đường đi ngắn nhất
procedure Dijkstra ;
begin
S := [1] ; { S chỉ chứa đỉnh nguồn }
for i:=2 to n do
begin
D[i] := C[1, i] ; { Khởi đầu các giá trị cho D }
P[i] := 1 ; { Khởi đầu các giá trị cho P }
end ;
for i:=1 to n - 1 do
begin
Lấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ;
Thêm w vào S ;
for mỗi đỉnh u thuộc V - S do
if (D[w] + C[w, u] < D [u]) then
begin
D[u] := D[w] + C[w, u] ; P[u] := w ;
end ;
end;
end;
3/Ví dụ :
8
Tìm đường đi ngắn nhất
Áp dụng giải thuật Dijkstra cho đồ thị hình sau:
<!--[if !supportLineBreakNewLine]-->
9
Tìm đường đi ngắn nhất
procedure DijksTra;
begin
t:=false;
t[u0]:=true;
d[i]:=c[u0,i];{Neu khong co duong di thi d[i]=i’}
k:=1;{Da ket nap duoc 1 dinh}
while kdo
begin
{Tim min}
min:=i’;
for i:=1 to n do
if (d[i]
u:=i;
min:=d[u]
end;
t[u]:=true;{thêm u vao tập đỉnh}
inc(k);
{Tính lại đường đi}
for i:=1 to n do
if d[i]>d[u]+c[u,i] then
if not((d[i]=i’)and(d[u]=i’)and(c[u,i]=i’)) then
begin
d[i]:=d[u]+c[u,i];
truoc[i]:=u
10
Tìm đường đi ngắn nhất
end
end;
if d[v0]=i’ then
KhongCoDuongDi
else
QuayLaiMangTruocDeTimDuong
end;
Chương 3: Mô tả chung và code:
1.1 Mô tả chung và kí hiệu:
Ký hiệu dùng trong giải thuật Dijkstra
Tập đỉnh đã được sắp thứ tự 0… n-1 , (có n đỉnh), với s là đỉnh gốc.
giá trị của phần tử a[i][j] là độ dài từ i-◊Ma trận kề A=[i,j] >j , [Vậy nếu
a[i][j]=0, giữa i và j không có cạnh nối nhau].
Mark[i] = 1 : đã chọn (đỉnh i đã được chọn vào cây T), Mark[i]=0:
ngược lại, [Mark là mảng có n phần tử dùng để đánh dấu một đỉnh i đã
được chọn vào cây T hay chưa]
pr[i]: đỉnh trước đỉnh i (ví dụ: pr[6]=3, đỉnh 3 là đỉnh trước khi tới đỉnh
6), [pr : (previous) là mảng có n phần tử dùng để truy tìm ngược lại đỉnh
trước(đỉnh cha) của một đỉnh nào đó]
d[i]: giá trị của phần tử d[i] là độ dài đường đi nối từ s->i (s là đỉnh
gốc), [d là mảng có n phần tử, giá trị của phần tử thứ i chính là độ dài của
s->i]
Ý tưởng giải Dijkstra
11
Tìm đường đi ngắn nhất
Ta sẽ xây dựng một cây phủ tối tiểu T từ một đỉnh s là đỉnh gốc của
cây.
Ở mỗi bước lặp: chọn một đỉnh i ở ngoài cây T, sao cho đỉnh này nối
được với cây, mà có đường đi tới gốc s là ngắn nhất. Dừng lặp khi T đã đủ
n đỉnh.
Vậy kết quả là cây T cuối cùng là cây phủ, có đỉnh gốc là s đi tới các
đỉnh còn lại bất kỳ là ngắn nhất.
Thủ tục
Khởi tạo:
Gốc s; d=vocuc; d[s]=0
Mark=0;
Mark[s]=1; [chọn s là một đỉnh trong cây T, (s là đỉnh gốc)]
d=a[s][i]; [lưu lại độ dài từ s đến tất cả đỉnh i (lấy ra được từ ma trận
kề) vào mảng d]
pr[i]=s; [đỉnh s là đỉnh trước(đỉnh cha) của tất cả các đỉnh còn lại]
Ở mỗi bước lặp trong thuật toán Dijkstra
1) Tìm k: d[k] = min {d[j]: Mark[j] =0 }, [k là đỉnh được chọn từ tất cả các đỉnh j
nằm ngoài cây T (tức là Mark[j]=0), sao cho khoảng cách từ s->k (tức là d[k]) là
nhỏ nhất so với các khoảng cách từ s->j (tức là d[j]) ]
2) Cập nhật:
Mark[k] = 1;
Với mọi đỉnh j mà Mark[j]=0
Nếu d[k]+a[k][j] < d[j] thì
12
Tìm đường đi ngắn nhất
d[j] = d[k]+a[k][j];
pr[j] = k;
Giải thích phần cập nhật:
Mark[k] = 1, [chọn đỉnh k vào cây T]
Mark[j]=0, [chỉ chọn đỉnh j chưa được đánh dấu (còn nằm ngoài cây T)
]
d[k]+a[k][j] < d[j], [nếu khoảng cách từ s->j (tức là d[j]) mà lớn hơn
khoảng cách từ s->k->j (tức là d[k]+a[k][j] ) thì chọn lại đường đi ngắn nhất
từ s->j sẽ đi qua k (s->j->k)]
d[j] = d[k]+a[k][j], [độ dài từ s->j (tức là d[j]) bằng với độ dài từ s->k (tức
là d[k]) và từ k->j (tức là a[k][j]).]
pr[j]=k, [đỉnh k là đỉnh trước khi tới j]
KẾT LUẬN
Bài báo cáo của em đã cố gắng tổng hợp đầy đủ những nội dung cơ bản liên
quan đến đề tài ” Tìm đường đi ngắn nhất bằng phương pháp Dijikstra” .
Xin chân thành cảm ơn!
TÀI LIỆU THAM KHẢO
1. />%E1%BA%A5t />
%C3%A3_%C4%91i_tu%E1%BA%A7n
13
Tìm đường đi ngắn nhất
14
