09HCB
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

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  

 

 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