maynghien
11-04-2009, 11:30 PM
bài này tui tự làm thôi nhe, thấy lớp DH tin học 07 đang tìm ráo riết quá nên post lên cho anh em xem thử thôi, nhờ mọi người góp ý. Các bạn ráng tạo thêm file dothi.txt các chỉ số cách nhau bởi dấu khoảng trắng và ký tự xuống dòng, chỉ số đầu tiên là số đỉnh của đồ thị, các chỉ số tiếp theo là ma trận liên kết(nhớ là đối xứng nhé). vd:
3
0 2 1
2 0 3
1 3 0
#include "stdio.h"
#include "conio.h"
#define MAX 100
#define VOCUC 300
typedef struct
{
int n;
int l[MAX][MAX];
}GRAPH; //ma tran lien thong cua do thi
typedef struct
{
int S[MAX]; //kiem tra xoa hoac chua
int tr[MAX]; //dinh lien truoc tren duong di
int L[MAX]; //khoang cach den dinh dau tien
}DUONGDI;
int readfile (GRAPH &g)//DOC FILE dothi.txt vao do thi g
{
int t;
FILE *f=fopen("Dothi.txt","rt");
if(f==NULL)
{
printf("Khong doc duoc file.");
return 0;
}
fscanf(f,"%d",&t);
g.n=t;
for (int i=0;i<g.n;i++)
for(int j=0;j<g.n;j++)
{
fscanf(f,"%d",&t);
g.l[i][j]=t;
}
fclose(f);
return 1;
}
void hienthidothi(GRAPH g)//hien thi ma tran lien ket
{
printf("So dinh cua do thi: %d\n",g.n);
for(int i=0;i<g.n;i++)
{
for(int j=0;j<g.n;j++)
printf("%4d",g.l[i][j]);
printf("\n");
}
}
int dijkstra(GRAPH g,DUONGDI &d,int dinhdau,int dinhcuoi)
{
int i;
for (i=0;i<g.n;i++)
{
d.S[i]=1;//cac dinh deu nam trong s
d.L[i]=VOCUC;//do dai cua moi dinh deu bang vo cuc
d.tr[i]=-1;//chua co dinh truoc tat ca cac dinh trong do thi
}
d.L[dinhdau]=0;//do dai cua dinh dau la 0
int min,v;
//xong phan khoi tao
while (d.S[dinhcuoi]==1)
{
min=VOCUC;
v=-1;
for (i=0;i<g.n;i++)//tim dinh co khoang cach ngan nhat den dinh dau
if(d.S[i]!=0 && min>= d.L[i])
{
min=d.L[i];
v=i;
}
if(min==VOCUC)
{
return 0;
break;
}//neu khong con dinh trong thanh phan lien thong chua dinh dau thi thoat ra
d.S[v]=0;//xoa dinh v
for (i=0;i<g.n;i++)//tim khoang cach den cac dinh gan V thoa dk if
if(g.l[v][i]>0)
if((d.L[i]) > (d.L[v]+g.l[v][i]))
{
d.L[i]=d.L[v]+g.l[v][i];
d.tr[i]=v;
}
}
return 1;
}
void xuat(DUONGDI d,GRAPH g,int dinhcuoi,int dinhdau)
{
// xuat duong di tu cuoi ve dau.
int i=dinhcuoi;
printf("Duong di:%3d",dinhcuoi);
while(i!=dinhdau)
{
printf("%3d",d.tr[i]);
i=d.tr[i];
}
printf("\n\nDo dai: %d",d.L[dinhcuoi]);
}
void main()
{
GRAPH g;
DUONGDI d;
if(readfile(g))
hienthidothi(g);
int dd=0;
int dc=4;
if( dijkstra(g,d,dd,dc))
{
printf("\n");
xuat(d,g,dc,dd);
}
else printf("khong co duong di");
getch();
}
3
0 2 1
2 0 3
1 3 0
#include "stdio.h"
#include "conio.h"
#define MAX 100
#define VOCUC 300
typedef struct
{
int n;
int l[MAX][MAX];
}GRAPH; //ma tran lien thong cua do thi
typedef struct
{
int S[MAX]; //kiem tra xoa hoac chua
int tr[MAX]; //dinh lien truoc tren duong di
int L[MAX]; //khoang cach den dinh dau tien
}DUONGDI;
int readfile (GRAPH &g)//DOC FILE dothi.txt vao do thi g
{
int t;
FILE *f=fopen("Dothi.txt","rt");
if(f==NULL)
{
printf("Khong doc duoc file.");
return 0;
}
fscanf(f,"%d",&t);
g.n=t;
for (int i=0;i<g.n;i++)
for(int j=0;j<g.n;j++)
{
fscanf(f,"%d",&t);
g.l[i][j]=t;
}
fclose(f);
return 1;
}
void hienthidothi(GRAPH g)//hien thi ma tran lien ket
{
printf("So dinh cua do thi: %d\n",g.n);
for(int i=0;i<g.n;i++)
{
for(int j=0;j<g.n;j++)
printf("%4d",g.l[i][j]);
printf("\n");
}
}
int dijkstra(GRAPH g,DUONGDI &d,int dinhdau,int dinhcuoi)
{
int i;
for (i=0;i<g.n;i++)
{
d.S[i]=1;//cac dinh deu nam trong s
d.L[i]=VOCUC;//do dai cua moi dinh deu bang vo cuc
d.tr[i]=-1;//chua co dinh truoc tat ca cac dinh trong do thi
}
d.L[dinhdau]=0;//do dai cua dinh dau la 0
int min,v;
//xong phan khoi tao
while (d.S[dinhcuoi]==1)
{
min=VOCUC;
v=-1;
for (i=0;i<g.n;i++)//tim dinh co khoang cach ngan nhat den dinh dau
if(d.S[i]!=0 && min>= d.L[i])
{
min=d.L[i];
v=i;
}
if(min==VOCUC)
{
return 0;
break;
}//neu khong con dinh trong thanh phan lien thong chua dinh dau thi thoat ra
d.S[v]=0;//xoa dinh v
for (i=0;i<g.n;i++)//tim khoang cach den cac dinh gan V thoa dk if
if(g.l[v][i]>0)
if((d.L[i]) > (d.L[v]+g.l[v][i]))
{
d.L[i]=d.L[v]+g.l[v][i];
d.tr[i]=v;
}
}
return 1;
}
void xuat(DUONGDI d,GRAPH g,int dinhcuoi,int dinhdau)
{
// xuat duong di tu cuoi ve dau.
int i=dinhcuoi;
printf("Duong di:%3d",dinhcuoi);
while(i!=dinhdau)
{
printf("%3d",d.tr[i]);
i=d.tr[i];
}
printf("\n\nDo dai: %d",d.L[dinhcuoi]);
}
void main()
{
GRAPH g;
DUONGDI d;
if(readfile(g))
hienthidothi(g);
int dd=0;
int dc=4;
if( dijkstra(g,d,dd,dc))
{
printf("\n");
xuat(d,g,dc,dd);
}
else printf("khong co duong di");
getch();
}