Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Thuật toán DIJKSTRA tìm đường đi ngắn nhất

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Thuật toán DIJKSTRA tìm đường đi ngắn nhất

Bài gửi  admin on Sat Dec 19, 2009 1:11 pm

Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất


Có n thành phố biết rằng đường đi giữa các thành phố (nếu có) là đường đi hai chiều. Sơ đồ mạng lưới giao thông của n thành phố cho bởi ma trận A[i,j] trong đó:
- A[i,j] là độ dài đường đi từ thành phố i đến thành phố j.
- A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.
- A[i,j] = A[j,i]
- A[i,j] nguyên, không âm.
Hãy xác định đường đi ngắn nhất từ thành phố D đến thành phố C.
Dữ liệu vào: đồ thị đã liên thông và cho trong file Bai7.inp với nội dung
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng thứ hai lưu đỉnh D và đỉnh C.
- Dòng i+2 (0Dữ liệu ra: xuất ra màn hình đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được.

Bai7.inp Kết quả:
6 DUONG DI NGAN NHAT LA: 5
1 6 1->2->4->6
0 1 2 0 0 0
1 0 2 2 3 0
2 2 0 5 4 0
0 2 5 0 3 2
0 3 4 3 0 4
0 0 0 2 4 0

Bai7.inp Kết quả:
6 DUONG DI NGAN NHAT LA: 8
1 6 1->2->4->6
0 1 4 0 0 0
1 0 2 6 5 0
4 2 0 7 3 0
0 6 7 0 0 1
0 5 3 0 0 3
0 0 0 1 3 0

Code:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define FileIn "Bai7.inp"
/*Đọc file dữ liệu bài toán*/
void Doc_File(int**A, int &n, int &D, int &C){
   FILE*f = fopen(FileIn,"rb");
   fscanf(f,"%d%d%d",&n,&D,&C);
   cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl;
   *A = new int [n];
   for(int i =0;i<n;i++) {
      A[i] = new int [n];
      for(int j =0;j<n;j++) {
         fscanf(f,"%d",&A[i][j]);
         cout<<A[i][j]<<" ";
      }
      cout<<endl;
   }
   fclose(f);
   D--; C--;
}
/*Thuật toán Dijkstra tìm đường đi ngắn nhẩt từ đỉnh D đến đỉnh C*/
void Dijkstra(int **A, int n, int D, int C) {
   char *DanhDau = new char[n];
   int *Nhan = new int[n];
   int *Truoc = new int[n];
   int XP, min;
   for(int i=0; i<n; i++){
      Nhan[i] = MAXINT;
      DanhDau[i] = 0;
      Truoc[i] = D;
   }
   Nhan[D] = 0;
   DanhDau[D] = 1;
   XP = D;
   while(XP != C){
      for(int j=0; j<n; j++)
      if(A[XP][j]>0 && Nhan[j]>A[XP][j]+Nhan[XP] && DanhDau[j]==0) {
         Nhan[j] = A[XP][j]+Nhan[XP];
         Truoc[j] = XP;
      }
      min = MAXINT;
      for(j = 0; j<n; j++)
      if(min>Nhan[j]&& DanhDau[j]==0){
         min = Nhan[j] ;
         XP = j ;
      }
      DanhDau[XP] = 1;
   }
   cout<<”Duong Di Ngan Nhat La:”<<Nhan[C]<<endl;
   cout<<C+1<<” <- “<<Truoc[C]+1;
   i = Truoc[C];
   while(i!=D){
      i = Truoc[i];
      cout<<” <- “<<i+1;
   }
}
/*Chương trình chính*/
void main() {
   int**A,n,Dau,Cuoi;
   Doc_File(A,n,Dau,Cuoi);
   Dijkstra(A,n,Dau,Cuoi);
   delete*A;
   getch();
}


Được sửa bởi admin ngày Thu Oct 04, 2012 1:50 pm; sửa lần 1.
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Re: Thuật toán DIJKSTRA tìm đường đi ngắn nhất

Bài gửi  admin on Tue Jun 07, 2011 4:09 pm

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.

Bài toán
Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị.
Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường (và do đó là không âm). Chúng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi.
Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C.

Thuật toán
Thuật toán Dijkstra có thể mô tả như sau:
Ta quản lý một tập hợp động S. Ban đầu S={s}.
Với mỗi đỉnh v, chúng ta quản lý một nhãn d[v] là độ dài bé nhất trong các đường đi từ nguồn s đến một đỉnh u nào đó thuộc S, rồi đi theo cạnh nối u-v.
Trong các đỉnh ngoài S, chúng ta chọn đỉnh u có nhãn d[u] bé nhất, bổ sung vào tập S. Tập S được mở rộng thêm một đỉnh, khi đó chúng ta cần cập nhật lại các nhãn d cho phù hợp với định nghĩa.
Thuật toán kết thúc khi toàn bộ các đỉnh đã nằm trong tập S, hoặc nếu chỉ cần tìm đường đi ngắn nhất đến một đỉnh đích t, thì chúng ta dừng lại khi đỉnh t được bổ sung vào tập S.
Tính chất không âm của trọng số các cạnh liên quan chặt chẽ đến tính đúng đắn của thuật toán. Khi chứng minh tính đúng đắn của thuật toán, chúng ta phải dùng đến tính chất này.

Chứng minh
Ý tưởng của chứng minh như sau.
Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá trị của đường đi ngắn nhất từ nguồn s đến v.
Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v đến v.
Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu tiên như vậy.
Đường đi của ta có dạng s - ... - w - ... - v. Nhưng do trọng số các cạnh không âm nên đoạn s - ... - w có độ dài không lớn hơn hơn toàn bộ đường đi, và do đó có giá trị bé hơn d[v]. Mặt khác, do cách chọn w của ta, nên độ dài của đoạn s - ... - w chính là d[w]. Như vậy d[w] < d[v], trái với cách chọn đỉnh v. Đây là điều mâu thuẫn. Vậy điều giả sử của ta là sai. Ta có điều phải chứng minh.

    Hôm nay: Mon Nov 20, 2017 4:29 pm