Thuật toán Dijkstra

_­­THUẬT TOÁN DIJKSTRA

Bài viết sau được tổng hợp từ nhiều nguồn trên Internet.

http://vi.wikipedia.org

Thuật toán Dijkstra, mang tên nhà khoa học máy tính người Hy Lạp, Edsger Dijkstra, 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 với trọng số không â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ô cùng]  và một đỉnh nguồn s. Cần tính toán đường đi ngắn nhất từ đỉnh s tới mỗi đỉnh của đồ thị.

Ví dụ:

Chúng ta dùng các đỉnh của đồ thị để mô tả các thành phố và dùng các cạnh để mô tả đường đi giữa chúng. Khi đó trọng số của các cạnh có thể xem như độ dài đường đi( và do đó 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ẽ chỉ cho ta đường đi ngắn nhất 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 2 đỉnh đầu mút của chúng.

MÔ TẢ:

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ừ đỉnh s đến một đỉnh u nào đó thuộc S , rồi đi theo cạnh nối u-v.

GIẢ MÃ

Phân tích:

Với giải thuật trên dễ dàng thực hiện trên các đồ thị kích thước nhỏ, để mã hóa và cài đặt hiệu quả cần đưa thêm các  cấu trúc dữ liệu để sử dụng trong giải thuật.

Dữ liệu:

+Hàm d[u] dùng để lưu trữ độ dài đường đi ngắn nhất từ đỉnh s đến đỉnh u.  

Rõ ràng: d[s] = 0

Ký hiệu:

X(u) là tập hợp tất cả các đỉnh có cạnh nối tới u

Nếu với mọi v thuộc X(u)  đã xác định được d[v] thì:

d(u) = min{d[v] + w(v,u), v thuộc X(u) }

trong đó: w(v,u) = độ dài cạnh nối trực tiếp u-v

+Ta sẽ mặc đỉnh w(v,u) = (vô cùng) nếu giữa v-u không tồn tại cạnh nối (Thông thường nó được gán một giá trị lớn hơn hoặc  bằng tổng độ dài của các cạnh của đồ thị).

Những đỉnh đã được tính d[v] hữu hạn được cho vào một hàng đợi có ưu tiên.   Hàng đợi này luôn được bổ sung và sắp xếp hợp lý là cấu trúc đống nhị phân (Heap).

+Để theo dõi  trạng thái của các đỉnh trong quá trình xét, ta dùng hàm color(u) xác định với mọi v thuộc V. Lúc đầu các đỉnh được tô màu trắng (white), khi cho vào hàng đợi ta tô màu xám(Gray), khi đã tính xong khoảng cách ta tô màu đen (Black).

+Nếu cần ghi lại đường đi ta sẽ phải dùng hàm con trỏ Pre(u) để chỉ đỉnh đứng trước đỉnh u trên đường đi ngắn nhất từ s tới u.

MÃ:

/*:
 Dua theo :
  Bai giang ky thuat lap trinh
  Bien soan: Ths.Nguyen Duy Phuong (HVCNBCVT)
 Thuat toan Dijkstra mo ta bang thu tuc Dijkstra
 
*/

void Dijkstra(void)
{
    (*Dau vao G= (V,E) voi n dinh co ma tran trong so A[u,v]>=0, s thuoc V*)
    (*Dau ra la khoang cach nho nhat tu s den cac dinh con lai d[v]: v thuoc V
        Truoc[v] ghi lai dinh truoc v trong duong di ngan nhat tu s den v*)

     (*Buoc 1: Khoi tao nhan tam thoi cho cac dinh*)
     for(v=1;v<=n;++v)
     {
   d[v] = A[s,v];
   truoc[v] = s;
     }
     d[s] = 0;
     T = V\{s}; (*T la tap dinh co nhan tam thoi*)
     while(T != rong)
     {
            (*Buoc lap*)
            Tim dinh u thuoc T sao cho d[u] = min{d[z]: z thuoc T}
            T = T\{u}; (*Cố định nhãn cho đỉnh u*)
            For(v thuoc T)
            {
                (*Gan lai nhan cho cac dinh trong T*)
    if(d[v] > d[u] + A[v,u])
    {
     d[v] = d[u] + A[v,u];
     truoc[v] = u;
    }
            }
     }
}

//Nguon code lay tu: https://sandynguyen.wordpress.com
#include<fstream>
#include<iostream>
#include<stdlib.h>
#define MAX 101
using namespace std;

ifstream fi("dijkstra_input.txt");
ofstream fo("dijkstra_output.txt");

int a[MAX][MAX]; //Ma tran ke duong di
int n; //So dinh
int b[MAX] = {0}; //Mang danh dau di qua
int d[MAX], trace[MAX]; //Mang khoang cach va danh dau truy hoi
const int z = 32767; //Hang so dai dien cho vo cung

//==============================================================================
void Dijkstra(int s)
{
 b[s] = 1; //Danh dau vi tri s da duoc di qua
 trace[s] = 0; //Danh dau khong the truy hoi ve khong
 //Khoi tao mang d va trace ban dau
 for(int i =1;i<=n;++i)
 {
  if(b[i]!=1)
  {
   d[i] = a[s][i]; //d[i] luu khoang cach duong di tu s->i
   trace[i] = s; //Dinh truoc s la i
  }
 }
 int min, val;
 //Duyet qua n-2 lan (Bo qua lan cuoi vi khong con dinh nao de di)
 for(int i =1;i<n-1;++i)
 {
  val = z; //Khoi tao val bang gia tri vo cung
  //Tim dinh nho nhat ma khoang cach nho nhat va chua di qua
  for(int k =1;k<=n;++k)
  {
   if(d[k]<val&&b[k] == 0) //Neu khong cach tu s->k nho hon val va k chua di qua
   {
    val = d[k];
    min = k; //Dinh can tim luc nay la k
   }
  }
  b[min] = 1; //Danh dau dinh min da xet
  //Tu dinh nay di tiep den cac dinh khac xem co toi uu hon khong
  for(int j =1;j<=n;++j)
  {
   if(d[j] > d[min] + a[min][j])
   {
    d[j] = d[min] + a[min][j]; //Gan khoang cach tu s->j bang khoang cach nho hon khac
    trace[j] = min; //Truoc dinh j la dinh min
   }
  }
 }
}

//Ham goi de quy truy tim duong di
void Trace(int s, int e)
{
 do
 {
  fo<<e<<" ";
  e = trace[e];
 }while(e!=0); // Vong lap ket thuc khi khong con dinh nao nam ke sau dinh e
}

int main()
{
 if(!fi.is_open())
 {
  cout<<"Error. Can't open the file.";
     system("pause");
 }
 //Nhap so dinh
 fi>>n;
 //Nhap do thi va khoi tao gia tri ban dau
 for(int i =1;i<=n;++i)
 {
  for(int j =1;j<=n;++j)
  {
   fi>>a[i][j];
   if(a[i][j] == -1)
     a[i][j] = z;
     //Neu khong ton tai duong di truc tiep tu i->j,
     //gan  khoang cach giua chugn bang vo cung
  }
 }
 
 int start, end; //Vi tri bat dau va ket thuc
 fi>>start>>end;
 //Goi thuat toan dijkstra de di den cac dinh
 Dijkstra(start); //Duyet bat dau tu dinh start
 //Xuat ket qua
 fo<<"Cac dinh di qua: ";
 Trace(start,end);
 fo<<"\n Tong chi phi: "<<d[end];
 fi.close();
 fo.close();
 return 0 ;
}

*