VD: bài tập demo

Bai1.inp Kết quả:
6 DUONG DI NGAN NHAT LA: 5
1 6 1->2->4->6
0 1 2 0 0 0
1 0 2 2 3 0
2 2 0 5 4 0
0 2 5 0 3 2
0 3 4 3 0 4
0 0 0 2 4 0

Bai1.inp Kết quả:
6 DUONG DI NGAN NHAT LA: 8
1 6 1->2->4->6
0 1 4 0 0 0
1 0 2 6 5 0
4 2 0 7 3 0
0 6 7 0 0 1
0 5 3 0 0 3
0 0 0 1 3 0

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define FileIn "Bai1.inp"
/*Đọc file dữ liệu bài toán*/
void Doc_File(int**A, int &n, int &D, int &C){
   FILE*f = fopen(FileIn,"rb");
   fscanf(f,"%d%d%d",&n,&D,&C);
   cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl;
   *A = new int [n];
   for(int i =0;i<n;i++) {
      A[i] = new int [n];
      for(int j =0;j<n;j++) {
         fscanf(f,"%d",&A[i][j]);
         cout<<A[i][j]<<" ";
      }
      cout<<endl;
   }
   fclose(f);
   D--; C--;
}
/*Thuật toán Dijkstra tìm đường đi ngắn nhẩt từ đỉnh D đến đỉnh C*/
void Dijkstra(int **A, int n, int D, int C) {
   char *DanhDau = new char[n];
   int *Nhan = new int[n];
   int *Truoc = new int[n];
   int XP, min;
   for(int i=0; i<n; i++){
      Nhan[i] = MAXINT;
      DanhDau[i] = 0;
      Truoc[i] = D;
   }
   Nhan[D] = 0;
   DanhDau[D] = 1;
   XP = D;
   while(XP != C){
      for(int j=0; j<n; j++)
      if(A[XP][j]>0 && Nhan[j]>A[XP][j]+Nhan[XP] && DanhDau[j]==0) {
         Nhan[j] = A[XP][j]+Nhan[XP];
         Truoc[j] = XP;
      }
      min = MAXINT;
      for(j = 0; j<n; j++)
      if(min>Nhan[j]&& DanhDau[j]==0){
         min = Nhan[j] ;
         XP = j ;
      }
      DanhDau[XP] = 1;
   }
   cout<<”Duong Di Ngan Nhat La:”<<Nhan[C]<<endl;
   cout<<C+1<<” <- “<<Truoc[C]+1;
   i = Truoc[C];
   while(i!=D){
      i = Truoc[i];
      cout<<” <- “<<i+1;
   }
}
/*Chương trình chính*/
void main() {
   int**A,n,Dau,Cuoi;
   Doc_File(A,n,Dau,Cuoi);
   Dijkstra(A,n,Dau,Cuoi);
   delete*A;
   getch();
}