PDA

View Full Version : Bác nào có lòng hảo tâm test giùm em bài tập về đồ thị với ạ



SUPER KUNG FU
23-05-2009, 13:23
#include<math.h>
#include<conio.h>
#include<stdio.h>
#define maxV 20

int A[maxV][maxV];
int T[maxV];
int V;
void NhapMT();
void XuatMT();
void DocMTKe();
void Dijkstra();
void InDuongDi_ksdTruoc(int s, int t);
FILE *fn;


void main()
{
int s,t;
NhapMT();
// DocMTKe();
XuatMT();
printf("Nhap dinh dau, dinh cuoi cua duong di: ");
scanf("%d %d", &s, &t);
Dijkstra();
InDuongDi_ksdTruoc(s,t);
getch();
}

void NhapMT()
{
int i,j;
printf("Nhap so dinh cua ma tran ke :");
scanf("%d",&V);
fn=fopen("C:\\test.txt","w");
fprintf(fn,"%d\n",V);
for(i=1;i<=V;i++)
{
for(j=1;j<=V;j++)
{
printf("A[%d,%d] = ",i,j);
scanf("%d",&(A[i][j]));
}
}
printf("Ghi vao file\n");
for(i=1;i<=V;i++)
{
for(j=1;j<=V;j++)
{
fprintf(fn,"%3d",A[i][j]);

}
fprintf(fn,"\n");
}
}

void XuatMT()
{
int i,j;
printf("\nMa tran ke:\n");
for (i=1; i<=V; i++)
{
for (j=1; j<=V; j++)
printf("%3d ", A[i][j]);
printf("\n");
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DocMTKe()
{
int i,j;
fn = fopen("C:\\test.txt", "r");
if (fn == NULL)
{
printf("Doc file loi !!!");
}
fscanf(fn, "%d", &V);
for (i=1; i<=V; i++)
{
for (j=1; j<=V; j++)
{
fscanf(fn,"%d", &(A[i][j]));
}
}
fclose(fn);
printf("%d",V);

}

void Dijkstra()
{
int *d;
int s;
int Truoc[20];

for (int v=0; v<V; v++)
{
d[v] = A[s][v];
Truoc[v] = s;
}
d[s] = 0;
T[s] = 1;
while ( 1 )
{
int u = -1;
for (int z=0; z<V; z++)
if (T[z] != 1 && (u==-1 || d[u] > d[z]))
u = z;
if (u == -1)
break;
T[u] = 1;
for (int v=0; v<V; v++)
if (T[v]!=1 && d[v]>d[u]+A[u][v])
{
d[v] = d[u]+A[u][v];
Truoc[v] = u;
}
}

}

void InDuongDi_ksdTruoc(int s, int t)
{
int d[20];
int STACK[20], topS = 0;
STACK[topS++] = t;
int v = t;
while ( v != s )
{
int v = STACK[topS-1];
for (int u = 0; u<V; u++)
if (d[v] == d[u]+A[u][v])
break;
if ( u == V)
break;
STACK[topS++] = u;
v = u;
}
printf("Duong di tu %d den %d la",s,t);
for ( int i=topS-1; i>=0; i-- )
printf("%d ",STACK[ i ] +1);
}