Tìm đường đi ngắn nhất (thứ tự topo)

[ductam]

Trong trường hợp đồ thị có số đỉnh tương đối lớn và đồ thị không có chu trình ta có thể đánh số lại các đỉnh của đồ thị sao cho mỗi cạnh của đồ thị được nối từ đỉnh có chỉ số nhỏ sang đỉnh có chỉ số lớn.
Để cải thiện thời gian ta sử dụng queue trong phần đánh lại các đỉnh. Các bạn nghiên cứu code trong New_Number sẽ thấy sử dụng queue chỗ nào. Như bài trước mình đã viết trong thực tế ta cài queue phải ngắn gọn, linh động không cứng nhắc lúc nào cũng Push(), Pop(),...
Việc thứ tự topo các bạn có thể tìm hiểu thêm.
http://www.uit.edu.vn/data/gtrinh/TN030/Htm/Bai10_4.htm
Còn phần lớn giống với cách cài đặt trong DIJKTRA mình đã viết trong bài trước.
Code chi tiết:

Code:


#include<stdio.h>
#include<conio.h>

#define maxN 100
#define maxC 100000000

const char *INP="TEST.INP";

int N,M,S,F;
long int d[maxN];
int trace[maxN];
long int c[maxN][maxN];
int queue[maxN];


void LoadGraph();
void New_Number();
void OutResult();
void Init();
void DIJKTRA_TOPO();


int main()
{
    LoadGraph();
    New_Number();
    Init();
    DIJKTRA_TOPO();
    OutResult();
    getch();
    return 0;   
}
void LoadGraph()
{
 FILE *f;
 int i,j,x,y,z;
 
 f=fopen(INP,"rb");   
 
 fscanf(f,"%d%d%d%d",&N,&M,&S,&F);
 
 for(i=1;i<=N;i++)
 {
  for(j=1;j<=N;j++) c[i][j]=maxC;
  c[i][i]=0;               
 } 
 
 for(i=1;i<=M;i++)
 {
  fscanf(f,"%d%d%d",&x,&y,&z);   
  c[x][y]=z;
 }
 fclose(f);
}
void New_Number()
{
 int u,v;
 int first,last;
 int deg[maxN];
 
 // Init queue
 first=0;
 last=-1;
 // Tinh ban bac vao cua cac dinh
 for(u=1;u<=N;u++)
 {
  deg[u]=0;
  for(v=1;v<=N;v++)
                  if(u!=v&&c[v][u]<maxC)
                  {
                    deg[u]++;                     
                  }     
 } 
 // Dua nhung dinh co ban bac vao deg bang 0 vao hang doi
 for(u=1;u<=N;u++) if(deg[u]==0)
                  {
                    last++;
                    queue[last]=u;           
                  }
 // Bat dau danh so cac dinh theo thu tu topo
 while(first<=last)
 {
  u=queue[first];
  first++;
  for(v=1;v<=N;v++)
                  if(c[u][v]<maxC)
                  {
                    deg[v]--;
                    if(deg[v]==0)
                    {
                    last++;
                    queue[last]=v;           
                    }               
                  }           
 }
}
void Init()
{
 int u;
 for(u=1;u<=N;u++)
 {
  d[u]=c[S][u];
  trace[u]=S;                 
 }
}
void DIJKTRA_TOPO()
{
 int i,j,u,v;
 for(i=1;i<N;i++)
 for(j=i+1;j<=N;j++)
 {
  u=queue[i];
  v=queue[j];
  if(d[v]>d[u]+c[u][v])
  {
                      d[v]=d[u]+c[u][v];
                      trace[v]=u; 
  }                 
 }   
}
void OutResult()
{
 int u;
 if(d[F]==maxC) printf("Khong co duong di tu %d -> %d",S,F);
 else
 {
      u=F;
      printf("Min(%d,%d)=%d\n",S,F,d[F]);
      while(u!=S)
      {
      printf("%d <- ",u);
      u=trace[u];         
      }
      printf("%d ",S);
 }   
}



Hi vọng những bài viết này sẽ giúp ích các bạn ít nhiều.