Bài 15-Cài đặt thuật toán Dijkstra

Cho đồ thị G = (V, E) có hướng, liên thông, có trọng số
f : E ®  và hai đỉnh u, v Î V. Hãy tìm đường đi a*(u, v)
sao cho độ dài đường đi (tổng trọng số) từ đỉnh u đến đỉnh v là ngắn nhất.

Ký hiệu T(u, v) là tập hợp các đường đi nối u với v trong đồ thị G, khi đó:

              m(a*) = min{m(a) : a Î T}.

Năm 1959, Edsger W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất này. Thuật toán thực hiện việc gán và giảm giá trị của nhãn tại mỗi đỉnh của đồ thị.

Độ dài đường đi a*(u, v) từ đỉnh u đến đỉnh v là ngắn nhất trong tất cả các đường đi từ u đến v. Sau đây sẽ xem xét và tìm hiểu tư tưởng của thuật toán này. Chẳng hạn, với đồ thị hình 5.8, ta cần tìm đường đi a*(2, 4) từ đỉnh 2 đến đỉnh 4 có độ dài là ngắn nhất.

- Sử dụng phương pháp "tham ăn" và sử dụng kỹ thuật gán nhãn đồ thị; phương pháp tham ăn ở đây là thực hiện gán nhãn cho tất cả các đỉnh kề với đỉnh hiện tại trên đường đi.

- Sử dụng tập S để lưu các đỉnh được chọn trên đường đi từ
u đến v.

- Tập V \ S là tập những đỉnh thuộc V nhưng không thuộc S.

Chương trình vidu52.cpp:

/* vidu52.cpp */

#include<stdio.h>

#include<conio.h>

#define MAX 20

typedef struct Cung

{

int d, c, ts; /*d: đỉnh đầu, c: đỉnh cuối và ts:   trọng số của cung */

};

int n, m; // n đỉnh, m cung

int S[MAX], VS[MAX];

int nhan[MAX];

int DD[MAX];

Cung DC[MAX];

void doctep()

{

  int d,c,ts;

  FILE *F = fopen("dothi58.inp","rt");

  if(F = = NULL)

     printf("\n Loi khi mo tep dothi56.inp!");

  else

  {

     fscanf(F,"%d %d\n",&n,&m);

     printf("\n n = %d, m = %d",n,m);

     for(int i = 1;i<= m;i++)

     {

        fscanf(F,"%d %d %d\n",&d,&c,&ts);

        DC[i].d = d; DC[i].c = c; DC[i].ts = ts;

        printf("\n %3d %3d %3d",DC[i].d,
                 DC[i].c,DC[i].ts);

     }

  }

  fclose(F);

}

int findmin_inVS()

{

  int i,min;

  for(i = 1;i<= n;i++)

     if(VS[i] = = 1)

     {

        min = i;

        break;

     }

  for(i = 1;i<= n;i++)

   if((VS[i] = = 1) && (nhan[i]<nhan[min]))

   {

        min = i;

        break;

   }

  return(min);

}

void innhan()

{

  for (int i = 1;i<= n;i++)

     printf("%3d,/,",nhan[i]);

}

void dijkstra(int u, int v)

{

  int i,j,k,l,d,c,ts;

  for(i = 1;i<= m;i++)

  {

     nhan[i] = 1000;

     S[i] = 0;

     VS[i] = 1;

  }

  /* nhan[i] không thể gán là -1 trong trường hợp
         này, vì phải dùng để so sánh */

  nhan[u] = 0;

  printf("\nNHAN KHOI TAO LA:");

  innhan();

  while(S[v] = = 0) // v chưa có trong S

  {

     int a = findmin_inVS();

     // tìm một đỉnh a nhỏ nhất trong V\S:

     S[a] = 1; // đưa a vào tập S

     VS[a] = 0; // xoá a ra khỏi tập V\S

     // duyệt trên các cung tìm đỉnh kề của đỉnh a

     printf("\n\tNhan la:"); innhan();

     for(int j = 1;j<= m;j++)

     {

        d = DC[j].d;

        c = DC[j].c;

        ts = DC[j].ts;

        if((d = = a) && (nhan[a]+ts<nhan[c]))

         nhan[c] = nhan[a]+ts;

     }

     printf("\nDinh a: %3d",a);

    getch();

  }

  printf("\nNhan cua cac dinh:");

  innhan();

  getch();

  // tìm đường đi

  k = v;

  l = 1;

  while(S[u] = = 1) // khi u vẫn nằm trong S

  {

     if (k = = u)

     {

        S[u] = 0;

        DD[l] = u;

     }

     for(j = 1;j<= m;j++)

     { d = DC[j].d; c = DC[j].c; ts = DC[j].ts;

       if((c = = k) && (nhan[k] = = nhan[d]+ts))

       {

           S[k] = 0;

           DD[l] = k;

           k = d;

           l++;

       }

        if((d = = k) && (nhan[k] = = nhan[c]+ts))

        {

           S[k] = 0;

           DD[l] = k;

           k = c;

           l++;

       }

     }

  }

  printf("\n Duong di:");

  for(i = l;i>= 1;i--)

  printf(" %3d",DD[i]);

}

void main()

{

  int u, v;

  clrscr();

  printf("\nTim duong di ngan nhat tren do thi G:
         co huong, lien thong, co trong so duong\n");

  doctep();

  u = 2; v = 4;

  dijkstra(u,v);

  printf("\nDo dai duong di tu%3d dinh den dinh%3d
         la: %3d", u, v, nhan[v]);

  getch();

}

Tham khảo: Nguyễn Trường Xuân và các tác giả, Lý thuyết đồ thị và ứng dụng, nxb Giáo dục Việt Nan, 2017. 

Bình luận

Bài viết khác

Bài 16- Thuật toán Ford -Fulkerson

Thuật toán Ford - Fulkerson  Việc chứng minh định lý luồng cực đại - lát cắt cực tiểu cho ta một thuật toán tìm luồng cực đại (thuật toán Ford- Fulkerson)

Bài 15-Cài đặt thuật toán Dijkstra

Năm 1959, Edsger W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. Thuật toán thực hiện việc gán và giảm giá trị của nhãn tại mỗi đỉnh của đồ thị.

Bài 14-Thuật toán Prim

Thuật toán Prim do Robert Prim đưa ra vào năm 1957, ý tưởng chính của nó là lần lượt ghép vào cây khung các cạnh có trọng số tối thiểu liên thuộc với một đỉnh của cây mà không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi có được n - 1 cạnh vào cây. Dưới đây là mô tả các bước của thuật toán Prim.

Bài 13-Cài đặt thuật toán Kruskal tìm cây khung tối thiểu

File dữ liệu về đồ thị dạng text;

ĐỐI TÁC CỦA CHÚNG TÔI