Kêu gọi các bạn đăng ký Thi OLP 2010

[ductam]

Nhằm chia sẽ những gì mà Tâm tích lũy được trong hai năm nghiên cứu. Mình xin Admin mở một topic có tên: Algorithm&Online_Judge:
Đầu tiên mình xin trình bày code bài Tìm đường đi ngắn nhất cài đặt chi tiết theo thuật toán DIJKTRA
Bài toán thì hầu như các bạn đều đã biết rồi nên mình không trình bày ở đây.
Các khai báo chi tiết:
#define maxN 100
với maxN là số đỉnh tối đa của bài toán
#define maxC 10000
với maxC là trọng số cực đại giữa hai đỉnh nào đó.
free[maxN]: đây là mảng đánh dấu đỉnh i đã được cố định nhãn chưa
Trong bài này mình cài đặt free[i]=1 nghĩa là đỉnh i chưa được cố định nhãn
free[i]=0 nghĩa là đỉnh i đã được cố định nhãn.
Còn cố định nhãn có nghĩa là gì mình sẽ giải thích sau.
c[maxN][maxN] là trọng số giữa hai đỉnh bất kì
Trong đó:
c[i][j]=0 nếu đỉnh i trùng đỉnh j.
c[i][j]=maxC nếu đỉnh i không có đường đi đến đỉnh j.
d[maxN] đó d[i]trong là khoảng cách nhỏ nhất giữa đỉnh S và đỉnh i.
Tư tưởng của thuật toán DIJKTRA, tại một bước lặp, tìm đỉnh u sao cho đỉnh u chưa cố định nhãn và có d[u] nhỏ nhất.
Cố định nhãn có ý nghĩa gì? Đơn giản là đỉnh u đã cố định nhãn thì giá trị d[u] là khoảng cách nhỏ nhất khi đi từ đỉnh xuất phát S đến đỉnh u.
Và khi tìm được đỉnh u thì duyệt qua tất cả các đỉnh v sao cho đỉnh v chưa cố định nhãn (nghĩa là d[v] chưa phải là giá trị khoảng cách nhỏ nhất khi đi từ đỉnh xuất phát S đến đỉnh v).
Công thức cố định nhãn v như sau:
d[v]=Min(d[v],d[u]+c[u][v]).
Quá trình lặp lại cho đến khi không tìm được đỉnh u hoặc đỉnh F đã được cố định.
Chương trình hoàn chỉnh như sau:

Code:


#include<stdio.h>
#include<conio.h>



#define maxC 100000000
#define maxN 101

const char *INP="TEST.INP";


int N,M,S,F;
long int c[maxN][maxN];
long int d[maxN];
int free[maxN];
int trace[maxN];

void LoadGraph();
void InitDistance();
void DIJKTRA();
void OutResult();
long int Min(long int x,long int y);

int main()
{
    LoadGraph();
    InitDistance();
    DIJKTRA();
    OutResult();
   
    getch();
    return 0;
}
void LoadGraph()
{
 int i,j,x,y,z;
 FILE *f;
 f=fopen(INP,"rb");
 fscanf(f,"%d%d%d%d",&N,&M,&S,&F); 
 
 for(i=1;i<=N;i++)
 {
                  for(j=1;j<=N;j++) c[i][j]=maxC;
                  c[i][i]=0;
 }
 
 for(i=1;i<=M;i++)
 {
  fscanf(f,"%d%d%d",&x,&y,&z);
  c[x][y]=z;
 }
 fclose(f);
}
void InitDistance()
{
    int i;
    // Ban dau tat ca cac dinh chua co dinh nhan
    for(i=1;i<=N;i++) free[i]=1;               
    // Khoi tao khoang cach nho nhat ban dau tu dinh S den tat ca cac dinh
    for(i=1;i<=N;i++)
    {
      d[i]=c[S][i];
      trace[i]=S;                 
    }
}
void DIJKTRA()
{
/*
B1: Tim dinh u chua co dinh va co d[u] nho nhat.
Neu tim duoc dinh u va dinh u khac dinh F sang B2
Nguoc lai thuat toan ket thuc.
B2: Co dinh dinh u va toi uu tat ca cac dinh v (dinh v chua co dinh nha) theo cong thuc:
    d[v]=Min(d[v],d[u]+c[u][v])
    thay doi trace[v]=u
*/   
      long int min=maxC;
      int i,u,v;
      while(1)
      {
        // tim dinh u
        u=0;       
        min=maxC;
        for(i=1;i<=N;i++) if(free[i]&&d[i]<min)
                        {
                          u=i;
                          min=d[i];
                        }       
        if(u==0||u==F) break;
        else
        {
        // co dinh dinh u   
        free[u]=0;     
        // Co dinh nhung dinh v ke voi dinh u va chua duoc co dinh nhan
        for(v=1;v<=N;v++) if(free[v]&&d[v]>d[u]+c[u][v])
                          {
                            d[v]=Min(d[v],d[u]+c[u][v]);
                            trace[v]=u;                // dinh truoc dinh v la dinh u
                          }
        }     
      }
}
long int Min(long int x,long int y)
{
 if(x>y) return y;
 return x;   
}
void OutResult()
{
 int v;
 v=F;
 if(d[F]==maxC) printf("khong co duong di tu %d den %d",S,F);
 else
 {
      printf("Min(%d,%d)=%ld\n",S,F,d[F]);
      while(v!=S)
      {
      printf("%d <- ",v);
      v=trace[v];         
      }
      printf("%d",S);
 }   
}


Chương trình trên chỉ tham khảo, còn trong nhiều bài toán áp dụng kiến thức tìm đương thì chúng ta cần phải chỉnh sửa sao cho phù hợp với đề bài.
Để chạy được code trên bạn cần phải tạo FILE TEST.INP và đặt cùng thư mục với code trên. Cách tạo file TEST.INP trong IDE Dev-C++ như sau:
Bạn File->New->SourceFile. Bạn gõ dữ liệu như sau:

Code:


6 7 1 4
1 2 1
1 6 20
2 3 2
3 4 20
3 6 3
5 4 5
6 5 4



Sau đó Save Bạn gõ tên "TEST.INP" và OK.

Bài toán tìm đường đi được áp dụng rất nhiều trong các bài toán thi OLP sinh viên cũng như giải các bài toán trên các trang Online_Judge. Có thể nói đây là bài toán cực kì cơ bản và ai tham gia OLP sinh viên cũng phải cài được và cài rất thuần thục.

Mình sẽ viết tiếp về hàng đợi (queue) và stack. Đây là hai cấu trúc sữ liệu cực kì cơ bản mà hầu như ai học tin học đều cũng phải biết.

[NinjaD3m0]

Thank anh Tâm góp ý kiến, em đã tạo thêm box. Mong anh post nhìu bài lập trình cho anh em ^^!

[ductam]

Thank you very much!!!!!!!!!!!!!!

[Sponsored content]