09HCB

Trang chủ 09HCB- Lớp Hoàn Chỉnh Đại Học Khoá 2009-2011
 
Trang ChínhTrang Chính  GalleryGallery  Tìm kiếmTìm kiếm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Share
 

 Bai Thuc Hanh 20100428

Go down 
Tác giảThông điệp
balo

balo

Tổng số bài gửi : 17
Join date : 16/03/2010

Bai Thuc Hanh 20100428 Empty
Bài gửiTiêu đề: Bai Thuc Hanh 20100428   Bai Thuc Hanh 20100428 Empty28/4/2010, 6:11 pm

THUAT TOAN DIJKSTRA (Tim duong di ngan nhat)

>>Chạy thuật toán Dijkstra (T.Lê Phong)
http://courses.fit.hcmus.edu.vn/file.php/795/Thuc_hanh/Chay_thuat_toan_Dijkstra.ppt


>>Thực hành (T.Lê Phong)
http://courses.fit.hcmus.edu.vn/file.php/795/Thuc_hanh/ThucHanh_DuongDiNganNhat.ppt


afro
Về Đầu Trang Go down
canary

canary

Tổng số bài gửi : 52
Join date : 17/03/2010

Bai Thuc Hanh 20100428 Empty
Bài gửiTiêu đề: Re: Bai Thuc Hanh 20100428   Bai Thuc Hanh 20100428 Empty28/4/2010, 11:00 pm

thanks
Về Đầu Trang Go down
balo

balo

Tổng số bài gửi : 17
Join date : 16/03/2010

Bai Thuc Hanh 20100428 Empty
Bài gửiTiêu đề: BAI LAM DE THAM KHAO   Bai Thuc Hanh 20100428 Empty6/5/2010, 12:39 am

Code:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define vocuc -1
typedef struct
{
int nVer;
int **a;
}Graph;

void Nhap(Graph &g);
void Xuat(Graph &g);
void DuongDiNganNhat_Dijkstra(Graph g,int dinhDau, int dinhCuoi);
void XuatDuongDi(Graph g,int dinhDau,int dinhCuoi,int LastV[]);
void main()
{
   Graph gp;
   Nhap(gp);
   //Xuat(gp);
   int dinhDau, dinhCuoi;
   printf("\nNhap dinh dau");
   scanf("%d",&dinhDau);
   printf("\nNhap dinh cuoi");
   scanf("%d",&dinhCuoi);
   DuongDiNganNhat_Dijkstra(gp,dinhDau,dinhCuoi);
   getch();
}

void XuatDuongDi(Graph g,int dinhDau,int dinhCuoi,int LastV[])
{
   int *duongdi=new int[g.nVer];
   int v=dinhCuoi;

   int id=0;
   while(v!=dinhDau)
   {
      duongdi[id]=v;
      v=LastV[v];
      id++;
   }
   duongdi[id]=dinhDau;
   int i;
   for(i=id;i>0;i--)
   {
      printf("%d -->",duongdi[i]);
   }
   printf("%d\n",duongdi[i]);

}

void DuongDiNganNhat_Dijkstra(Graph g,int dinhDau, int dinhCuoi)
{
   bool *thuocT=new bool[g.nVer];
   int *Length=new int[g.nVer];
   int *LastV=new int[g.nVer];
   //khoi tao cac gia tri ban dau
   //+cho tat ca cac dinh deu thuoc T
   //+do dai tai cac dinh deu bang vo cuc
   //+lastV cua tat ca cac dinh deu bang -1
   for(int i=0;i<g.nVer;i++)
   {
      thuocT[i]=true;
      Length[i]=vocuc;
      LastV[i]=-1;
   }
   // bat dau tu dinh dau
   //+Gan do dai dinh dau = 0
   Length[dinhDau]=0;

   while(true)
   {
   if(thuocT[dinhCuoi]==false)
      break;

   //chon dinh v thuoc T sao cho Length[v] nho nhat
   int v=-1;
   for(int i=0;i<g.nVer;i++)
   {
      if(thuocT[i]==true && Length[i] != vocuc)
         if(v==-1||Length[v]>Length[i])
            v=i;
   }
   thuocT[v]=false;

   //Cap nhat duong di

   for(int j=0;j<g.nVer;j++)
   {
      if(g.a[v][j]!=0&&thuocT[j]==true&&(Length[j]=vocuc || Length[j]>Length[v] + g.a[v][j]))
      {
         Length[j]=Length[v] + g.a[v][j];
         LastV[j]=v;
      }
   }
   }
   XuatDuongDi(g,dinhDau,dinhCuoi,LastV);
}

void Nhap(Graph &g)
{
FILE *f;
f=fopen("input.txt","rt");
fscanf(f,"%d",&g.nVer);

g.a=new int*[g.nVer];
for(int i=0; i<g.nVer;i++)
{
   g.a[i]=new int[g.nVer];
}

for(int i=0;i<g.nVer;i++)
{
   for(int j=0;j<g.nVer;j++)
   {
      fscanf(f,"%d",&g.a[i][j]);
   }
}
fclose(f);
}

void Xuat(Graph &g)
{
for(int i=0;i<g.nVer;i++)
{
   printf("\n");
   for(int j=0;j<g.nVer;j++)
   {
      printf("%d      ",g.a[i][j]);
   }
}
}
Về Đầu Trang Go down
dr.Answer

dr.Answer

Tổng số bài gửi : 18
Join date : 21/03/2010

Bai Thuc Hanh 20100428 Empty
Bài gửiTiêu đề: Re: Bai Thuc Hanh 20100428   Bai Thuc Hanh 20100428 Empty6/5/2010, 2:22 pm

balo đã viết:
Code:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define vocuc -1
typedef struct
{
int nVer;
int **a;
}Graph;

void Nhap(Graph &g);
void Xuat(Graph &g);
void DuongDiNganNhat_Dijkstra(Graph g,int dinhDau, int dinhCuoi);
void XuatDuongDi(Graph g,int dinhDau,int dinhCuoi,int LastV[]);
void main()
{
   Graph gp;
   Nhap(gp);
   //Xuat(gp);
   int dinhDau, dinhCuoi;
   printf("\nNhap dinh dau");
   scanf("%d",&dinhDau);
   printf("\nNhap dinh cuoi");
   scanf("%d",&dinhCuoi);
   DuongDiNganNhat_Dijkstra(gp,dinhDau,dinhCuoi);
   getch();
}

void XuatDuongDi(Graph g,int dinhDau,int dinhCuoi,int LastV[])
{
   int *duongdi=new int[g.nVer];
   int v=dinhCuoi;

   int id=0;
   while(v!=dinhDau)
   {
      duongdi[id]=v;
      v=LastV[v];
      id++;
   }
   duongdi[id]=dinhDau;
   int i;
   for(i=id;i>0;i--)
   {
      printf("%d -->",duongdi[i]);
   }
   printf("%d\n",duongdi[i]);

}

void DuongDiNganNhat_Dijkstra(Graph g,int dinhDau, int dinhCuoi)
{
   bool *thuocT=new bool[g.nVer];
   int *Length=new int[g.nVer];
   int *LastV=new int[g.nVer];
   //khoi tao cac gia tri ban dau
   //+cho tat ca cac dinh deu thuoc T
   //+do dai tai cac dinh deu bang vo cuc
   //+lastV cua tat ca cac dinh deu bang -1
   for(int i=0;i<g.nVer;i++)
   {
      thuocT[i]=true;
      Length[i]=vocuc;
      LastV[i]=-1;
   }
   // bat dau tu dinh dau
   //+Gan do dai dinh dau = 0
   Length[dinhDau]=0;

   while(true)
   {
   if(thuocT[dinhCuoi]==false)
      break;

   //chon dinh v thuoc T sao cho Length[v] nho nhat
   int v=-1;
   for(int i=0;i<g.nVer;i++)
   {
      if(thuocT[i]==true && Length[i] != vocuc)
         if(v==-1||Length[v]>Length[i])
            v=i;
   }
   thuocT[v]=false;

   //Cap nhat duong di

   for(int j=0;j<g.nVer;j++)
   {
      if(g.a[v][j]!=0&&thuocT[j]==true&&(Length[j]=vocuc || Length[j]>Length[v] + g.a[v][j]))
      {
         Length[j]=Length[v] + g.a[v][j];
         LastV[j]=v;
      }
   }
   }
   XuatDuongDi(g,dinhDau,dinhCuoi,LastV);
}

void Nhap(Graph &g)
{
FILE *f;
f=fopen("input.txt","rt");
fscanf(f,"%d",&g.nVer);

g.a=new int*[g.nVer];
for(int i=0; i<g.nVer;i++)
{
   g.a[i]=new int[g.nVer];
}

for(int i=0;i<g.nVer;i++)
{
   for(int j=0;j<g.nVer;j++)
   {
      fscanf(f,"%d",&g.a[i][j]);
   }
}
fclose(f);
}

void Xuat(Graph &g)
{
for(int i=0;i<g.nVer;i++)
{
   printf("\n");
   for(int j=0;j<g.nVer;j++)
   {
      printf("%d      ",g.a[i][j]);
   }
}
}

Bạn ơi, đường đi tìm ra không đúng rồi bạn à. Bạn thử test cái Matran của mình xem

7
0 9 -1 3 -1 -1 6
-1 0 8 -1 -1 -1 -1
-1 -1 0 -1 5 -1 -1
-1 4 1 0 8 -1 -1
-1 -1 -1 -1 0 17 -1
-1 -1 -1 -1 -1 0 12
-1 -1 -1 2 4 -1 0

Ket quả đúng là: 0 -> 3 -> 2 -> 4
Còn bạn sẽ ra kết quả khác á...Thậm chí có 1 cạnh không có đường đi tới:(
Về Đầu Trang Go down
Sponsored content




Bai Thuc Hanh 20100428 Empty
Bài gửiTiêu đề: Re: Bai Thuc Hanh 20100428   Bai Thuc Hanh 20100428 Empty

Về Đầu Trang Go down
 
Bai Thuc Hanh 20100428
Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
09HCB :: Lưu trữ :: HK1 :: LTDT-
Chuyển đến