Bai Thuc Hanh 20100428

#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]);
   }
}
}